动态规划算零钱兑换

/**
 * 零钱兑换
 * 有无限数量的多个面值的硬币，要求用最少的硬币凑出指定面值。
 * 假设面值为1,5,11，要求凑出15块钱。
 * 设f(n)为凑面值n的最少硬币函数。
 * 递归解法：
 *    f(15) = min(1 + f(14), 1 + f(10), 1 + f(4)) 意思即是：min(先凑1块再凑剩下的14块, 先凑 5块再凑剩下的10块，先凑11块再凑剩下的4块)
 *    这个是递归，和算fibonacci一样，中间会重复计算很多次。
 *    如果中间的计算结果能缓存起来就好了。
 *
 * 动态规划(DP)解法：
 *   用一个数组dp[]来缓存中间的计算结果，然后递归变成for循环。
 *
 *          最优解     1       5           11
 *  f(0)     0         0       0            0
 *  f(1)     1         1+f(0)  0            0
 *  f(2)     2         1+f(1)  0            0
 *  f(3)     3         1+f(2)  0            0
 *  f(4)     4         1+f(3)  0            0
 *  f(5)     1         1+f(4)  1+f(0)       0
 *  f(6)     2         1+f(5)  1+f(1)       0
 *  ....
 *
 */
public class MoneyExchange {

    public static void main(String[] args) {
        int[] array = new int[]{5 , 11, 1};
        //先排序，后面会用到
        Arrays.sort(array);
        int sum = 15;
        //从0~15共16个数字
        int[] dp = new int[sum + 1];
        //dp[0]=0, 从1开始循环，凑出从1块到15块的所有结果
        for (int i = 1; i < sum + 1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j : array) {
                if(i < j){
                    //array已经排过序，对单面值已经超过i的就不用计算了
                    break;
                }
                //当前面值取1张，然后从i中扣除当前面值，取剩下面值的最小张数
                min = Math.min(min, 1 + dp[i - j]);
            }
            dp[i] = min;
        }
        System.out.println(dp[sum]);
    }
}