Coin Change

Medium

完全背包问题：不限个数 + 目标装满 + 求最少硬币数

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.

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

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

Analysis

背包类问题:

• 每个元素可以取任意次；

• 只问最小的硬币数，就类似于 climbing stairs，只靠 sum 一个维度就可以了，但是循环依然是两层。

关于内外循环的顺序：此题中两者皆可。外循环为金额更直观一些。

Solution

以金额为外循环 （Preferred）

初始dp[i] = MAX; 其中 MAX = amount + 1, i = 1, ..., amount 是有前提假设的，即coins中最小的元素为1，这样最多有amount个硬币

public class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[n] = min number of coins to make amount n; 
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

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

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

硬币面值为外循环

public class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[n] = min number of coins to make amount n; 
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for(int j = 0; j < coins.length; j++){
            for(int i = coins[j]; i <= amount; i++){
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }

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

Another implementation

因为这里int MAX = Integer.MAX_VALUE;，要注意检查dp[j - coins[i]] != MAX，否则会整型溢出。

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        int MAX = Integer.MAX_VALUE;

        // dp[i] = min number of coins to make amount i; 
        int dp[] = new int[amount + 1];
        dp[0] = 0;

        for (int j = 1; j <= amount; j++) {
            dp[j] = MAX;
            for (int i = 0; i < coins.length; i++) {
                if (j >= coins[i] && dp[j - coins[i]] != MAX) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if (dp[amount] == MAX) {
            return -1;
        }
        return dp[amount];
    }
}

LeetCode Official Solution - Dynamic Programming

public 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 j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

DFS Recursive + Memoization

F(S) - minimum number of coins needed to make change for amount S using coin denominations [c0 … cn−1]

Then:

F(S)=F(S−C)+1

Recursion Search Tree: // [1, 2, 5] target = 6

// rec (6) // rec(6 - 1), rec(6 - 2), rec(6 - 5) // rec(6 - 1 - 1), rec(6 - 1 - 2), rec(6 - 1 - 5), rec(6 - 2 - 1), rec(6 - 5 - 1) // ... // rec(0) = 0

搜索树有许多重复的subproblem需要进行剪枝。

minCount[] - A memo to record visited & min coins for amount i

• if minCount[i] == -1, visited, but not reachable

• if minCount[i] == MAX, not visited

class Solution {

    private static int MAX;
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        // A memo to record visited & min coins for amount i
        int[] minCount = new int[amount + 1];
        MAX = amount + 1;
        Arrays.fill(minCount, MAX);

        int min = coinChanger(coins, amount, minCount);

        return min;
    }

    // minimum number of coins to sum to `amount`, if impossible, return -1
    private int coinChanger(int[] coins, int amount, int[] minCount) {
        if (amount == 0) {
            return 0;
        }
        if (minCount[amount] != MAX) {
            return minCount[amount];
        }

        int min = MAX;
        for (int i = 0; i < coins.length; i++) {
            if (amount >= coins[i]) {
                int tmp = coinChanger(coins, amount - coins[i], minCount);

                if (tmp != -1 && tmp < MAX) {
                    min = Math.min(min, tmp + 1);
                }
            }
        }
        minCount[amount] = min == MAX ? -1 : min;
        return minCount[amount];
    }
}

About repetition of elements: 循环的次序

By (@yuxiangmusic),

The difference is that if you updatedpwhile:

• increasing i then the previous partial result dp[i - coin] is the result that has considered coin already

• decreasing i then the previous partial result dp[i - coin] is the result that has not considered coin yet

/** 
 * @return number of ways to make sum s using repeated coins
 */
public static int coinrep(int[] coins, int s) {
    int[] dp = new int[s + 1]; 
    dp[0] = 1;          
    for (int coin : coins)      
        for (int i = coin; i <= s; i++)         
            dp[i] += dp[i - coin];                                  
    return dp[s];
}                                       

/**
 * @return number of ways to make sum s using non-repeated coins
 */
public static int coinnonrep(int[] coins, int s) {
    int[] dp = new int[s + 1];
    dp[0] = 1;  
    for (int coin : coins)
        for (int i = s; i >= coin; i--)
            dp[i] += dp[i - coin];              
    return dp[s];                                                   
}

Reference

https://leetcode.com/problems/coin-change/solution/

@mnmunknown - 8/2，背包问题