322. Coin Change

Difficulty: Medium

Related Topics: Dynamic Programming

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

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

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2- 1
• 0 <= amount <= 10

Solution

Language: Java

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        return dp(coins, amount, memo);
    }

    // 定义：使用不同面值的 coins 能凑成 amount 的最小数量
    private int dp(int[] coins, int amount, int[] memo) {
        // 出口
        // 1. amount == 0 意味着不用凑
        if(amount == 0) return 0;
        // 2. amount < 1 意味着没办法凑
        if(amount < 0) return -1;
        // 3. 如果我们已经求解过了，返回我们的解
        if(memo[amount] != Integer.MAX_VALUE) return memo[amount];

        // 做选择 
        // e.g. coins = [1,2,5] 我们有 3 个选择
        // 1. 选择面值为1的coin来凑
        // 2. 选择面值为2的coin来凑
        // 3. 选择面值为5的coin来凑
        // 因为我们需要求解的问题是 “能凑成 amount 的最小数量？”
        // 所以我们在每次选择中区一个最优的解
        // 那我们选择一个 coin 的 cost 是什么？
        // 答案就是每选择一个硬币，我们需要凑成 amount 的 coin 数量就要加一

        // 我们也可以把这个问题想成是一个树，去找到值为0的节点的最小深度
        int ans = Integer.MAX_VALUE;
        for(int coin : coins) {
            int rev = dp(coins, amount - coin, memo);
            // 取最小值，但是我们需要保证不是负值（出口2）
            if(rev >= 0 && rev < ans) {
                ans = rev + 1; 
            }
        }

        // 没办法做出选择
        if(ans == Integer.MAX_VALUE) {
            return memo[amount] = -1;
        } 

        return memo[amount] = ans;
    }
}