设有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 DP	public 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