硬币找零问题的动态规划实现

⼀，问题描述

给定⼀组硬币数，找出⼀组最少的硬币数，来找换零钱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 枚硬币，故使⽤的硬币数量要增1c[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代码实现

1 /** 2 *

3 * @param coinsValues 可⽤来找零的硬币 coinsValues.length是硬币的种类 4 * @param n 待找的零钱 5 * @return 最少硬币数⽬ 6 */

7 public static int charge(int[] coinsValues, int n){ 8 int[][] c = new int[coinsValues.length + 1][n + 1]; 9

10 //特殊情况1

11 for(int i = 0; i <= coinsValues.length; i++)12 c[i][0] = 0;

13 for(int i = 0; i <= n; i++)

14 c[0][i] = Integer.MAX_VALUE;15

16 for(int j_money = 1; j_money <=n; j_money++)17 {18

19 for(int i_coinKinds = 1; i_coinKinds <= coinsValues.length; i_coinKinds++)20 {

21 if(j_money < coinsValues[i_coinKinds-1])//特殊情况2，coinsValues数组下标是从0开始的, c[][]数组下标是从1开始计算的22 {

23 c[i_coinKinds][j_money] = c[i_coinKinds - 1][j_money];//只能使⽤ 第 1...(i-1)枚中的硬币24 continue;25 }26

27 //每个问题的选择数⽬---选其中较⼩的

28 if(c[i_coinKinds - 1][j_money] < (c[i_coinKinds][j_money - coinsValues[i_coinKinds-1]] +1))29 c[i_coinKinds][j_money] = c[i_coinKinds - 1][j_money];30 else

31 c[i_coinKinds][j_money] = c[i_coinKinds][j_money - coinsValues[i_coinKinds-1]] +1;32 }33 }

34 return c[coinsValues.length][n];35 }

①第28⾏-20⾏ 就是状态转换⽅程的表⽰。

②第16⾏-第19⾏的for循环体现就是动态规划的⾃底向上的思想。

复杂度分析：从代码19-20⾏的for循环来看，时间复杂度为O(MN)，M为可⽤的硬币种类数⽬，N为待找的零钱⾦额

从理论上分析，DP(Dynamic Programming)的时间复杂度为⼦问题的个数乘以每个⼦问题的可⽤选择数。显然，这个有MN个⼦问题，每个⼦问题有两种选择(选第i枚硬币和不选第i枚硬币)。

⼀直很好奇DP通过列⼀个⽅程就把⼀个问题给解决了，其实从16-19⾏的for循环来看，循环的下标是由⼩到⼤，说明它先解决⼦问题，然后再把原问题给解决了。

四，参考资料

http://haolloyin.blog.51cto.com/1177454/352115

五，完整代码

import java.util.Arrays;

public class DPCharge { /** *

* @param coinsValues 可⽤来找零的硬币 coinsValues.length是硬币的种类 * @param n 待找的零钱 * @return */

public static int charge(int[] coinsValues, int n){ int[][] c = new int[coinsValues.length + 1][n + 1];

//特殊情况1

for(int i = 0; i <= coinsValues.length; i++) c[i][0] = 0;

for(int i = 0; i <= n; i++)

c[0][i] = Integer.MAX_VALUE;

for(int j_money = 1; j_money <=n; j_money++) {

for(int i_coinKinds = 1; i_coinKinds <= coinsValues.length; i_coinKinds++) {

if(j_money < coinsValues[i_coinKinds-1])//特殊情况2 {

c[i_coinKinds][j_money] = c[i_coinKinds - 1][j_money]; continue; }

//每个问题的选择数⽬---选其中较⼩的

if(c[i_coinKinds - 1][j_money] < (c[i_coinKinds][j_money - coinsValues[i_coinKinds-1]] +1)) c[i_coinKinds][j_money] = c[i_coinKinds - 1][j_money]; else

c[i_coinKinds][j_money] = c[i_coinKinds][j_money - coinsValues[i_coinKinds-1]] +1; } }

return c[coinsValues.length][n]; }

public static void main(String[] args) { int[] coinsValues = {1,3,4};

Arrays.sort(coinsValues);//需要对数组排序,不然会越界..... int n = 6;

int minCoinsNumber = charge(coinsValues, n); System.out.println(minCoinsNumber); }}

原⽂：http://www.cnblogs.com/hapjin/p/5578852.html