[动态规划] — 322 – 零钱兑换

给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
复制代码

示例 2:

输入: coins = [2], amount = 3
输出: -1
复制代码

题目要求根据给定的总金额amount，从不同面值硬币中进行组合，最终找到能凑到amount所需的最少硬币的个数。我们无法直接根据给定的条件找出解，所以只能穷举所有的可能，然后从可能的情况中找到符合要求的解。既然需要穷举，那么可供选择的方法就有回溯和动态规划。而凑零钱这种问题显然存在最优子结构，如果我们知道了amount=m对应的硬币数，那么amount=m+1自然也可以得到相应的结果。因此，解决该题选择动态规划方法。

首先，我们先来思考一些基本的情况：如果 a m o u n t < 0 amount<0 amount<0，那么结果就是-1；如果 a m o u n t = 0 amount=0 amount=0，结果自然是0。但如果amount不是前面这两种特殊的值，那么就需要从给定的k种面值的硬币中找到满足题目要求的组合。假设给定的 a m o u n t = n amount=n amount=n，对于可选择面值的列表中的每一种面值m，我们可以做的选择是选还是不选：

如果选，那么看 a m o u n t − m amount – m amount−m有没有相应的最优解r。如果有，那么 a m o u n t = n amount=n amount=n的最优解自然就是 r + 1 r + 1 r+1。因为，在 a m o u n t − m amount – m amount−m最优解的前提下，只需要再多取一枚面值为m的硬币即可
如果不选，则继续判断下一个可能面值的硬币

遍历所有可能的面值，然后从所有可能的结果 r i r_{i} ri中找到值最小那个，它就是 a m o u n t = n amount=n amount=n的最优解。因此，总结上面思考的过程可写出动态转移方程：

f ( n ) = { 0 , n = < 0 0 , n = 0 min ⁡ ( f ( n − coin ⁡ ) + 1 , f ( n ) ) , n > 0 , coin ⁡ ∈ coin ⁡ s f(n)=\left\{\begin{array}{l} 0, n=<0 \\ 0, n=0 \\ \min (f(n-\operatorname{coin})+1, f(n)), n>0, \operatorname{coin} \in \operatorname{coin} s \end{array}\right. f(n)=⎩⎨⎧0,n=<00,n=0min(f(n−coin)+1,f(n)),n>0,coin∈coins
对应的解题代码如下：

/**
 * @Author dyliang
 * @Date 2020/8/13 23:27
 * @Version 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int k = 3;
        int[] coins = {1, 2, 5};
        int amount = 11;

        System.out.println(helper(k, amount, coins));
    }

    private static int helper(int k, int amount, int[] coins) {
        if (amount < 0){
            return -1;
        }
        if (amount == 0){
            return 0;
        }

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                // 如果amount小于给定的币值，直接考虑下一个面值
                if (i - coin < 0){
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        
        // 如果给定的amount不存在可能的组合，直接返回-1；否则返回对应的结果
        return (dp[amount] == mount + 1) ? -1 : dp[amount];
    }
}
复制代码