现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值？
m面值的货币，若分给n1的面值为n，则剩下的m-n面值让n2去拼，两种方法数相乘为此次分配的方法数。所以最终的方法数为f(0)*g(m-0) + f(1)*g(m-1) + … + f(m) * g(m-m)。 f 和 g 为两个动态规划问题。f为用n1中的货币的任意张数拼出x面值的方法数, g 为用n2中的货币的至多一张拼出x面值的方法数。
public class MoneyWays { public static int moneyWays(int[] arbitrary, int[] onlyone, int money) { if (money < 0) { return 0; } if ((arbitrary == null || arbitrary.length == 0) && (onlyone == null || onlyone.length == 0)) { return money == 0 ? 1 : 0; } int[][] dparb = getDpArb(arbitrary, money); int[][] dpone = getDpOne(onlyone, money); if (dparb == null) { return dpone[dpone.length-1][money]; } if (dpone == null) { return dparb[dparb.length-1][money]; } int res = 0; for (int i=0; i <= money; ++i) { res += dparb[dparb.length - 1][i] * dpone[dpone.length - 1][money - i]; } return res; } public static int[][] getDpArb(int[] arr, int money) { if (arr == null || arr.length == 0) { return null; } int[][] dp = new int[arr.length][money + 1]; for (int i=0; i<arr.length; ++i) { dp[i][0] = 1; } for (int i=1; arr[0]*i<=money; ++i) { dp[0][arr[0] * i] = 1; } for (int i = 1; i < arr.length; ++i) { for (int j = 1; j <= money; ++j) { dp[i][j] = dp[i-1][j]; dp[i][j] += j - arr[i] >= 0 ? dp[i][j-arr[i]] : 0; } } return dp; } public static int[][] getDpOne(int[] arr, int money) { if (arr == null || arr.length == 0) { return null; } int[][] dp = new int[arr.length][money+1]; for (int i=0; i < arr.length; ++i) { dp[i][0] = 1; } if (arr[0] <= money) { dp[0][arr[0]] = 1; } for (int i = 1; i < arr.length; ++i) { for (int j = 1; j <= money; ++j) { dp[i][j] = dp[i-1][j]; dp[i][j] += j - arr[i] >= 0 ? dp[i-1][j-arr[i]] : 0; } } return dp; } }
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
