动态规划解决换钱的方法数

简述题目：用1元，2元，5元，换成20元。一共有多少种换法。每一种纸币数量不限。暴力分析。直接利用每种纸币的限制条件穷举。方法简单直接。 public class StaticTest { public static void main(String[] args) { int num=0; for(int i=0;i<=20;i++) { for(int j=0;j<=10;j++) { for(int k=0;k<=4;k++) { int sum=0; sum=i+j*2+k*5; if (sum==20) { num++; System.out.println("1元"+i+" "+"2元"+j+" "+"5元"+k); } } } } System.out.println(num); } }

3很明显这个问题有最优子结构性质，和重复子问题。动态规划很合适解决。.动态规划解决思路：假设我们有i种货币，要换j钱。则有很多情况，第1种情况i种纸币不要，则方法数=dp[i-1][j],第2种情况i种货币取一个,则方法是=dp[i-1][j-1*第i种纸币的价值]，……..，直到第i种纸币数量*价值小于j. 4.直观展示。dp[i][j]表示用i种纸币，能换到j钱的方法数。其实如果能完成这个表格。就个问题就解决了。下面我们就用代码的方式来解决。 5.代码展示

public class ChangeMoney { public static void main(String[] args) { // TODO Auto-generated method stub int[] money={0,1,2,5}; int all=20; int[][] dp=new int[4][21]; //生成动态规划表 createTable(money,all,dp); System.out.println(dp[3][20]); } private static void createTable(int[] money, int all,int[][] dp) { // TODO Auto-generated method stub int temp; //这个地方其实有点写死。这里第一种纸币是1. for(int j=1;j<=20;j++) { dp[0][j]=0; } for(int j=0;j<=3;j++) { dp[j][0]=1; } for(int j=0;j<=20;j++) { dp[1][j]=1; } //初始化结束 for(int i=1;i<=3;i++) { for(int j=1;j<=20;j++) { int sum=0; temp=j/money[i]; //取i种纸币的次数 for(int k=0;k<=temp;k++) { sum+=dp[i-1][j-k*money[i]]; } dp[i][j]=sum; } } } }

6.结果比较。暴力和动态规划都是29种。 7.总结其实，我这个问题这个地方纸币是1，2，5。如果换成其它的。其它也很简单，根据其它的，把那个初始的地方，重新计算一下。就行了。思路明白才重要。其它这个问题还可以用回溯法解决。其它也很简单。就不介绍了。