322. 零钱兑换

题干

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

示例 1:

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

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一：暴力递归（超时）

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。

比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额 amount。

然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表 coins 中选择一个硬币，然后目标金额就会减少：

public static int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        if (amount < 0)
            return -1;
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subproblem = coinChange1(coins,amount - coin);
            //无解
            if(subproblem == -1) continue;
            res = Math.min(res, 1 + subproblem);
        }
        return res != Integer.MAX_VALUE ? res : -1;
    }

至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：
$F(n) = \begin{cases} 0, & \text{n=0} \\ -1, & \text{n<0} \\ min\{F(n-coin)+1|coin∈coins\}, & \text{n>0} \end{cases}$F(n)=⎩⎪⎨⎪⎧​0,−1,min{F(n−coin)+1∣coin∈coins},​n=0n<0n>0​

至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看：

时间复杂度分析：子问题总数 x 每个子问题的时间。

子问题总数为递归树节点个数，这个比较难看出来，是 $O(n^k)$O(nk)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 $O(k)$O(k)。所以总时间复杂度为 $O(k * n^k)$O(k∗nk)，指数级别。

方法二：带备忘录的递归/动态规划-自上而下

public static int coinChange(int[] coins, int amount) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        return dp(map, coins,amount);
    }
    public static int dp(HashMap<Integer,Integer> map, int[] coins, int amount) {
        if (amount == 0)
            return 0;
        if (amount < 0)
            return -1;
        if (map.containsKey(amount))
            return map.get(amount);
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subproblem = dp(map, coins,amount - coin);
            //无解
            if(subproblem == -1) continue;
            res = Math.min(res, 1 + subproblem);
        }
        map.put(amount, res != Integer.MAX_VALUE ? res : -1);
        return map.get(amount);
    }

不画图了，很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为$O(n)$O(n)。处理一个子问题的时间不变，仍是$O(k)$O(k)，所以总的时间复杂度是$O(kn)$O(kn)。

复杂度分析

• 时间复杂度：$O(kn)$O(kn)。
• 空间复杂度：$O(n)$O(n)，dp 使用的空间。

方法三：dp 数组的迭代解法/动态规划-自下而上

dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币。

public static int coinChange(int[] coins, int amount) {
        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        // base case
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 在求所有子问题 + 1 的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

复杂度分析

• 时间复杂度：$O(kn)$O(kn)。
• 空间复杂度：$O(n)$O(n)，dp 使用的空间。

参考文章

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie