DP初步：状态转移与递推
eg:
最少硬币问题有多个不同面值的硬币（任意面值）；数量不限； 输入金额S，输出最少硬币组合。思路：
int type[ ] = {1, 5, 10, 25, 50}; //5种面值硬币 定义数组 int Min[ ] 记录最少硬币数量：对输入的某个金额i，Min[i]是最少的硬币数量。第一步：
只考虑1元面值的硬币（把Min[]的变化叫做“状态转移”）
i=1元时，等价于：i = i-1 = 0元需要的硬币数量，加上1个1元硬币。
补：
把Min[]的变化叫做“状态转移”
继续
所有金额仍然都只用1元硬币
i=2元时，等价于：i = i-1 = 1元需要的硬币数量，加上1个1元硬币。i=3元时...i=4元时…
在1元硬币的计算结果基础上，再考虑加上5元硬币的情况。从i=5开始就行了：
i=5元时，等价于：
（1）i = i-5 = 0元需要的硬币数量，加上1个5元硬币。Min[5]=1。 （2）原来的Min[5]=5。 取（1）（2）的最小值，所以Min[5]=1用1元和5元硬币，结果：
递推关系： Min[i] = min(Min[i], Min[i - 5] + 1);
代码：
//ECUST luoyongjun #include<bits/stdc++.h> using namespace std; const int MONEY = 1001; //定义最大金额 const int VALUE = 5; //5种硬币 int type[VALUE] = {1, 5, 10, 25, 50}; //5种面值 int Min[MONEY]; //每个金额对应最少的硬币数量 void solve(){ for(int k = 0; k< MONEY; k++) //初始值为无穷大 Min[k] = INT_MAX; Min[0] = 0; for(int j = 0; j < VALUE; j++) for(int i = type[j]; i < MONEY; i++) Min[i] = min(Min[i], Min[i - type[j]] + 1); //递推式 } int main(){ int s; solve(); //提前计算出所有金额对应的最少硬币数量。打表 while(cin >> s) cout << Min[s] << endl; return 0; }扩展1：
打印最少硬币的组合
增加一个记录表 Min_path[i]，记录金额i需要的最后一个硬币。利用Min_path[]逐步倒推，就能得到所有的硬币。 Min_Path[6]=5：最后一个硬币是5元的；Min_Path[6-5]=Min_Path[1]=1，1元硬币；Min_Path[1-1]=Min_Path[0]=0，结束； 输出：硬币组合是“5元 + 1元”代码：
//ECUST luoyongjun #include<bits/stdc++.h> using namespace std; const int MONEY = 1001; //定义最大金额 const int VALUE = 5; //5种硬币 int type[VALUE] = {1,5,10,25,50}; //5种面值 int Min[MONEY]; //每个金额对应最少的硬币数量 int Min_path[MONEY]={0}; //记录最小硬币的路径 void solve(){ for(int k=0; k< MONEY;k++) Min[k] = INT_MAX; Min[0]=0; for(int j = 0;j < VALUE;j++) for(int i = type[j]; i < MONEY; i++) if(Min[i] > Min[i - type[j]]+1){ Min_path[i] = type[j]; //在每个金额上记录路径，即某个硬币的面值 Min[i] = Min[i - type[j]] + 1; //递推式 } } void print_ans(int *Min_path, int s) { //打印硬币组合 while(s){ cout << Min_path[s] << " "; s = s - Min_path[s]; } } int main() { int s; solve(); while(cin >> s){ cout << Min[s] << endl; //输出最少硬币个数 print_ans(Min_path,s); //打印硬币组合 } return 0; }扩展2：
硬币组合方案有多少？
hdu 2069题 有5种面值的硬币：1分、5分、10分、25分、50分。输入一个钱数S，输出组合方案的数量。例如11元，有4种组合方案：11个1分、2个5分 + 1个1分、1个5分 + 6个1分、1个10分 + 1个1分。S ≤ 250，硬币数量NUM ≤ 100。思路：
定义状态为dp[i][j]，建立一个“转移矩阵”，如下表。
横向是金额（题目中i ≤ 250），纵向是硬币数（题目中最多用100个硬币，j ≤ 100）。
矩阵元素dp[i][j]的含义是：用j个硬币实现金额i的方案数量。
矩阵元素dp[i][j] 例如表中dp[6][2] = 1，表示用2个硬币凑出6分钱，只有1种方案：5分+1分。表中的空格为0，即没有方案，例如dp[6][1]=0，用1个硬币凑6分钱，不存在这样的方案。表中列出了dp[10][7]以内的方案数。第一步：
只用1分硬币实现。 初始化：dp[0][0] = 1 dp[1][1] = dp[1][1] + dp[1-1][1-1] = dp[1][1] + dp[0][0] = 1。dp[1-1][1-1]的意思是：在1分金额中减去1分硬币的金额；原来1个硬币也减少1个。在这次状态转移中，dp[1][1]与dp[1-1][1-1]等价。第二步：
加上5分硬币，继续进行组合。 dp[i][j]，i < 5时，组合中不可能有5分硬币。当i≧5时，金额为i，硬币为j个的组合数量，等价于在i中减去5分钱，而且硬币数量也减去1个（即这个面值5的硬币）的情况。dp[i][j] = dp[i][j] + dp[i-5][j-1] 。第三步：
陆续加上10分、25分、50分硬币，同理有dp[i][j] = dp[i][j] + dp[i-type[k]][j-1]，k=2, 3, 4。代码：
//ECUST luoyongjun #include<bits/stdc++.h> using namespace std; const int COIN = 101; //题目要求不超过100个硬币 const int MONEY = 251; //题目给定的钱数不超过250 int dp[MONEY][COIN] = {0}; // DP转移矩阵 int type[5] = {1, 5, 10, 25, 50}; //5种面值 void solve() { // DP dp[0][0] = 1; for(int i=0; i<5; i++) for(int j=1; j<COIN; j++) for(int k = type[i]; k < MONEY; k++) dp[k][j] += dp[k-type[i]][j-1]; } int main() { int s; int ans[MONEY] = {0}; solve(); //用DP计算完整的转移矩阵 for(int i=0; i< MONEY; i++) //对每个金额，计算有多少种组合方案。打表 for(int j=0; j<COIN; j++) //从0开始，注意 dp[0][0]=1 ans[i] += dp[i][j]; while(cin >> s) cout << ans[s] << endl; return 0; }
