题目：：
用一套给定的硬币，求有多少种组合方式构成给定的数额，（不同指的是数量不同）
思路；
动态规划：dp[i]表示构成 i 金额的组合方法；
初始化：dp[i]=0;(无可构成硬币)
转移方程：对于每种硬币(x)，dp[x]++;当硬币面值大于时，dp[i]+=dp[i-x];
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ld long double 5 const int maxn=305; 6 int dp[maxn]; 7 int main() 8 { 9 memset(dp,0,sizeof(dp)); 10 int n,c,a; 11 scanf("%d%d",&n,&c); 12 for(int i=1;i<=c;i++) 13 { 14 scanf("%d",&a); 15 dp[a]+=1; 16 for(int k=a+1;k<=n;k++) 17 { 18 dp[k]+=dp[k-a]; 19 } 20 } 21 printf("%d\n",dp[n]); 22 return 0; 23 }
原文：https://www.cnblogs.com/sj-gank/p/11499049.html