DP 换硬币问题
设有n种不同面值的硬币，现要用这些面值的硬币来找开待凑钱数m，可以使用的各种面值的硬币个数不限。
找出最少需要的硬币个数，并输出其币值。
package DP;import java.util.Arrays;/** * A country has coins with denominations * 1 = d1 < d2 < · · · < dk. * * You want to make change for n cents, using the smallest number */public class CoinChange {public static int MEM[] = new int[10001]; // Can support up to 10000 peso value public static int coins[] = {1, 2, 3}; // Available coin denominations public static void main(String[] args) { int n = 321; System.out.println(CC(n) + ", " + CC_DP(n)); } // 记忆化搜索，top-down 递归 public static int CC(int n) { if(n < 0) return Integer.MAX_VALUE -1; else if(n == 0) return 0; else if(MEM[n] != 0) // If solved previously already return MEM[n]; else { // Look for the minimal among the different denominations MEM[n] = 1+CC(n-coins[0]); for(int i = 1; i < coins.length; i++) MEM[n] = Math.min(MEM[n], 1+CC(n-coins[i])); return MEM[n]; } } // bottom-up DPpublic static int CC_DP(int n){int[] minCoins = new int[n+1];Arrays.fill(minCoins, Integer.MAX_VALUE);// 第一个硬币minCoins[0] = 0;// 算出n前的每一个可换硬币的数量for(int i=1; i<=n; i++){// 根据递推公式，看看硬币可拆分的可能性for(int j=0; j<coins.length; j++){if(coins[j] <= i){minCoins[i] = Math.min(minCoins[i], 1+minCoins[i-coins[j]]);}}}return minCoins[n];}}