一，问题描述

给定一组硬币数，找出一组最少的硬币数，来找换零钱N。

比如，可用来找零的硬币为: 1、3、4   待找的钱数为 6。用两个面值为3的硬币找零，最少硬币数为2。而不是 4，1，1

因此，总结下该问题的特征：①硬币可重复多次使用。②在某些情况下，该问题可用贪心算法求解。具体可参考：某种 找换硬币问题的贪心算法的正确性证明

二，动态规划分析

为了更好的分析，先对该问题进行具体的定义：将用来找零的硬币的面值存储在一个数组中。如下：

coinsValues[i] 表示第 i 枚硬币的面值。比如，

第 i 枚硬币     面值

    1                1

    2                3

    3                4

待找零的钱数为 n （上面示例中 n=6）

为了使问题总有解，一般第1枚硬币的面值为1

考虑该问题的最优子结构：设 c[i,j]表示 可用第 0，1，.... i 枚硬币 对 金额为 j 的钱 进行找钱 所需要的最少硬币数。

i 表示可用的硬币种类数， j 表示 需要找回的零钱

第 i 枚硬币有两种选择：用它来找零 和 不用它找零。因此，c[i,j]的最优解如下：

c[i,j]= min{c[i-1,j] , c[i, j-coinsValues[i]] + 1}   其中，

c[i-1,j] 表示 不使用第 i 枚硬币找零时，对金额为 j 进行找钱所需要的最少硬币数

c[i, j-coinsValues[i]] + 1 表示 使用 第 i 枚硬币找零时，对金额为 j 进行找钱所需要的最少硬币数。由于用了第 i 枚硬币，故使用的硬币数量要增1

c[i,j] 取二者的较小值的那一个。

另外，对特殊情况分析（特殊情况1）一下：

c[0][j]=Integer.MAXVALUE ，因为 对 金额为 j 的钱找零，但是可用的硬币面值 种类为0，这显然是无法做到的嘛（除非是强盗:） )

其实这是一个”未定义“的状态。它之所以初始为Integer.MAXVALUE，与《背包九讲》中的”当要求背包必须装满的条件下，价值尽可能大“时 的初始化方式一样。

c[i][0]=0，因为，对 金额为0的钱 找零，可用来找零的硬币种类有 i 种，金额为0啊，怎么找啊，找个鸭蛋啊。

其实，边界条件是根据具体的问题而定的。DP太博大了，理解的不深。

另外，还有一种特殊情况(特殊情况2)，就是： coinsValues[i] > j

这说明第 i 枚硬币的面值大于 金额 j ，这也不能用 第 i 枚硬币来找零啊，（欠你5块钱，但是找你一张百元大钞）不然就亏了了(吃亏是福啊^~^...or 杀鸡焉用牛刀!!!)

有了这个特征转移方程：c[i,j]= min{c[i-1,j] , c[i, j-coinsValues[i]] + 1}  ，就好写代码了。

三，JAVA代码实现