人民币有1、2、5、10、20、50、100这几种面值。 现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。 比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。 输入有多组，每组一行，为一个整合n。 输入以0结束。 输出该面额有几种表示方法。 使用动态规划解决：
#include <iostream> #include<string> #include<vector> #include<algorithm> #include <fstream> using namespace std; int money[7] = { 1, 2, 5, 10, 20, 50, 100 }; long int dp[7][250]; int main() { int i, j, n; for (i = 0; i < 7; i++) { dp[i][0] = 1; } for (i = 0; i < 250; i++) //以上两个循环为，当钱的类型为1时，都只有一种零钱方法，即全部为1块的 { dp[0][i] = 1; } for (i = 1; i < 7; i++)//代表零钱类型， { for (j = 1; j < 250; j++)//j代表输入的钱数 { if (j - money[i] >= 0) dp[i][j] = dp[i][j-money[i]] + dp[i-1][j]; //最优子结构,dp[i-1][j]:钱数为j，在i-1的钱类型时拥有的最大分配种数。 //dp[i][j-money[i]]:钱数为j-money[i]，在i的钱类型时拥有的最大分配种数，因为是累积关系，所以要加上dp[i-1][j] else dp[i][j] = dp[i-1][j]; } } while (cin >> n && n != 0) { cout << "类型总数 = " << dp[6][n] << endl; } return 0; }