动态规划解决硬币问题

动态规划

动态规划步骤

1.观察最后一步,逆推之前步骤

2.确定方程

3.设置条件

4.计算

例题

如果有2,5,7三种硬币,用最少的硬币凑满50元钱

假设凑满50元钱最少要用n个硬币,则f(50)=n;

最后一枚硬币是2,5,7三种情况都存在

最后一枚是2 则f(50) = 1+ f(48)

最后一枚是5 则f(50) = 1+ f(45)

最后一枚是7则f(50) = 1+ f(43)

故可推得f(x) = Math.min(f(x-2)+1,1+ f(x-5),1+ f(x-7));

f(0) = 0 明显成立,如果f(x)明显不存在,则设为最大值,如Integer.Max

代入数字

f(1) = Math.min(f(-1)+1,1+ f(-4),1+ f(-6)) = max

f(2) = Math.min(f(0)+1,1+ f(-5),1+ f(-7)) = 2;

@Test
    public void method() {
        int amount = 27;
        int[] coins = new int[]{2,5,7};
        int[] result = new int[amount+1];
        result[0] = 0;
        for (int i = 1; i <=amount; i++) {
            result[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                //1.金额要大于该硬币面值 2.f(x)不是最大值,即不能没有最小硬币结果
                if (i-coins[j]>=0&&result[i-coins[j]]!=Integer.MAX_VALUE){
                    result[i] = Math.min( result[i], result[i-coins[j]]+1);
                }
            }
        }
        if (result[amount]==Integer.MAX_VALUE){
            System.out.println("不存在");
        }else{
            System.out.println(result[amount]);
        }
    }