动态规划（三）

有n种硬币，面值为v1…vn，数量无限，选用硬币，使其和金额为s，要求求出最少的硬币组合。

首先我们应该有打表的思想，将任意金额的最少硬币组合数量存到一个数组里，输入一个金额时就可以直接查询数组中对应的硬币最少数量。

定义一个int Min[MONEY]，Min[i]是金额i对应的最少硬币数量。Min[i]这样记录子问题最优解的数据称为“状态”。

讲解以5种面值（1、5、10、25、50）的硬币为例：

第一步：只使用1分硬币。 初始值Min[0] = 0，表示0个硬币可以表示0金额，其他的Min[i]为无穷大。 那Min[1]如何计算？ 这时可以在Min[0]的基础上加一个1分硬币，此时Min[1] = Min[0] + 1 = Min[1] = Min[1-1] +1 。 此时可以推导出第一个递推公式： Min[i] = min(Min[i]，Min[i-1]+1) 故只用1分硬币的组合结果如下：

第二步：在使用1分硬币的基础上增加第二大面值的5分硬币 此时要在第一步状态的基础上从金额为5开始转换（若金额小于5时，不能用5分硬币替换） i = 5时，相当于在i = 0的基础上加一个5分硬币，得到Min[5] = Min[5-5] +1 = 1。 1分硬币+5分硬币组合的结果如下： 第一步i=5时，只用1分硬币状态的结果Min[5] = 5，此时根据推导公式Min[i] = min(Min[i]，Min[i-5]+1) 可知，Min[5-5]+1=1比 Min[5]=5更小，故Min[5]=1。

第三步：继续处理其他面值的硬币。 接下来就是在第二步的基础上将面值为10的硬币转换。 例如i= 10时，相当于在i = 0的基础上加了一个10分硬币，此时Min[10] = Min[10-10] + 1 = 1。 又第二步中Min[10] = 2， 故Min[10] = min(Min[10] ，Min[10-10]+1) = Min[10-10]+1 = 1。

所以找出规律，所有面值的递推公式都是： Min[i] = min（Min[i]，Min[i-面值]+1）

代码如下：