LeetCode 322. Coin Change

Problem

LeetCode 322. Coin Change

1. 题目简述

给出一些面值的硬币coins，和目标金额mount，找出最少需要多少枚硬币能够组成amount，如果无法组成，则返回-1。例如：

Example 1：

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

2. 算法思路

相关问题：

1. LeetCode 39. Combination Sum
2. LeetCode 40. Combination Sum II
3. LeetCode 216. Combination Sum III

经典老题目，我们需要留意的是它和combination sum的区别，combination sum是找具体的组合，而coin change只要找最小的合法组合。因此，这道题我们考虑用dp，而不是回溯法。

那么如何找到最优子问题呢？对于例子中的amount为11，它有几种组合方式：（1）10 + 1 （2）9 + 2 （3）6 + 5，找出这三者中最小的即可。其base case是当amount为0的时候，组合方式有且只有一种。递推式如下：

$$dp[i] = Math.min(dp[i - coin] + 1, dp[i]) (for coin in coins)$$

动态规划（top-down）

初始化的值没必要设置成Integer.MAX_VALUE，最大设置为amount+1即可，因为最多也就是amount个1元硬币。

class Solution {
    // 注意和combination sum的区别，combination sum是要找所有的解决方案，所以采用回溯，这里只要找最少的那个就好了。
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        return getMinCoins(coins, amount, dp, amount + 1);
    }

    private int getMinCoins(int[] coins, int amount, int[] dp, int max) {
        if (amount < 0) {
            return -1;
        } else if (amount == 0) {
            return 0;
        }

        if (dp[amount] != 0) {
            return dp[amount];
        }

        // 这里不用min，直接用dp[amount]直接操作也可以的！！！
        // dp[amount] = max + 1;
        // for (int coin : coins) {
        //     int temp = getMinCoins(coins, amount - coin, dp, max);
        //     dp[amount] = temp == -1 ? dp[amount] : Math.min(dp[amount], temp + 1);
        // }
        //dp[amount] = dp[amount] == max + 1 ? -1 : dp[amount];

        int min = max + 1;
        for (int coin : coins) {
            int temp = getMinCoins(coins, amount - coin, dp, max);
            min = temp == -1 ? min : Math.min(min, temp + 1);
        }

        dp[amount] = min == max + 1 ? -1 : min;
        return dp[amount];
    }
}

动态规划（Bottom-up）

这里我们需要注意的只有边界case，也就是dp[0] = 0，这里要和coin change 2进行区分，那个是求方式，这个是求硬币数，不一样的！！！

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] >= max ? -1 : dp[amount];
    }
}