题意：手中的硬币币值有1,5,10,25,50共5种，给定一个面值n，问把n兑换成硬币的方案总数是多少。
分析：先打表，再输入输出。动态规划的简单题目，设dp[i]表示面值为i的情况下能兑换的种类，那么dp[i]=sigma(dp[i-v[j]]), j=0..4, v[j]={1,5,10,25,50};也就是，如果i大于v[j]，说明能够用dp[i-v[j]]的方案再加上一枚面值为v[j]的硬币作为面值i的方案，不过这只是方案中硬币的数量多了一枚，题目中只是问方案数量，那么此时两者在方案数量上等价，那么方案总数上加上这一种情况就可以了。
代码：
View Code
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 using namespace std; 5 #define DEBUG 6 const int MAXN = 7500; 7 int dp[MAXN]; 8 int main(){ 9 #ifndef DEBUG 10 freopen("in.txt", "r", stdin); 11 #endif 12 int i, j; 13 int v[5] = {1, 5, 10, 25, 50}; 14 memset(dp, 0, sizeof dp); 15 dp[0] = 1; 16 for(i=0; i<5; i++) 17 for(j=1; j<MAXN; j++) 18 if(j>=v[i]) dp[j]+=dp[j-v[i]]; 19 int n; 20 while(scanf("%d", &n)!=EOF) printf("%d\n", dp[n]); 21 return 0; 22 }
