322.Coin Change

Tags: [dp], [knapsack], [complete_knapsack]

Com: {t}, {t_review}

Hard: [####]

Link: https://leetcode.com/problems/coin-change/#/description

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:
coins =[1, 2, 5], amount =11
return3(11 = 5 + 5 + 1)

Example 2:
coins =[2], amount =3
return-1.

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

Better Solution: DP, Complete Knapsack (optimized)

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if not coins or not amount:
            return 0

        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for a in xrange(1, amount + 1):
                if coin <= a:
                    dp[a] = min(dp[a], dp[a - coin] + 1)

        return dp[amount] if dp[amount] <= amount else -1

Revelation:

• 内层循环从左向右，例如当前coin = 1，然后开始内层循环，amount从1开始：

coin = 1
a = 1, dp[1] = min(dp[1], dp[1 - 1] + 1) = min(dp[1], dp[0] + 1)
a = 2, dp[2] = min(dp[2], dp[2 - 1] + 1) = min(dp[1], dp[1] + 1)
a = 3, dp[3] = min(dp[3], dp[3 - 1] + 1) = min(dp[1], dp[2] + 1)
... ...
其实这个过程就是一直在往‘背包’中放入coin = 1.
这也就是为什么内从循环从左向右，是在不断的多次放入同一种‘商品‘入’背包‘.

• 如果内层循环是从右向左，意思是，每种物品只放一次，这就是0-1背包的优化的解法.

Note:

• Time complexity = O(len(coins) * amount).

Solution DP, Complete Knapsack

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if not amount:
            return 0
        if not coins:
            return -1

        # Complete Knapack Problem.
        # DP formula:
        # f[i][sub_amount] = min((put 0 current coin), (put 1 current coin), (put 2 current coins), ... , (put k current coins))
        # f[i][sub_amount] = min(f[i - 1])[sub_amount - k * current_coin] + k, k = 0, 1, 2, ...

        f = [[amount + 1 for _ in xrange(amount + 1)] for _ in xrange(len(coins) + 1)]
        for i in xrange(len(coins) + 1):
            f[i][0] = 0

        for i in xrange(1, len(coins) + 1):
            coin = coins[i - 1]
            for sub_amount in xrange(amount + 1):
                tmp_min = f[i - 1][sub_amount]
                k = 0
                while k * coin <= sub_amount:
                    tmp_min = min(tmp_min, f[i - 1][sub_amount - k * coin] + k)
                    k += 1

                f[i][sub_amount] = tmp_min

        if f[len(coins)][amount] > amount:
            return -1
        return f[len(coins)][amount]

Revelation:

• For 0-1 Knapsack Problem, for each stuff we have two choices: one is choosing, the other one is not choosing. Then we want to find the min or max among these two choices.
• So for 0-1 Knapsack Problem, the DP formula is f[i][amount] = min or max (f[i - 1][amount], f[i - 1][amount - cost] + benefit)
• For Complete Knapsack Problem, for each stuff we have multiple choices: choosing 0 current stuff, choosing 1 current stuff, choosing 2 current stuff, ..., choosing k current stuff. Then we want to find the min or max among these multiple choices.
• So for Complete Knapsack Problem, the DP formula is f[i][amount] = min or max (f[i - 1][amount - k * cost] + k * benefit), k = 0, 1, 2, ...
• If we don't need fully fill the "bag" (or "amount"), we can initialize f like this: f[i][all] = 0.
• If we need fully fill the "bag" or ("amount"), we can initialize f like this: f[i][0] = 0, f[i][other] = min_int or max_int.

Note:

• Time complexity = O(len(coins) * amount * k), under the worst case k = amount / min(coins), so the time complexity = O(len(coins) * amount * (amount / min(coins))).

Better Java Solution:

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0 || amount == 0) {
            return 0;
        }

        // DP formula:
        // f[i][amount] = min(f[i - 1][amount],
        //                    f[i][amount - k*[i]] + k)
        int [][] f = new int [coins.length + 1][amount + 1];
        for (int i = 0; i <= coins.length; i ++) {
            for (int a = 0; a <= amount; a ++) {
                if (a == 0) {
                    f[i][a] = 0;
                } else {
                    f[i][a] = amount + 1;
                }
            }
        }

        for (int i = 1; i <= coins.length; i ++) {
            int currCoin = coins[i - 1];

            for (int a = 1; a <= amount; a ++) {
                f[i][a] = f[i - 1][a];
                int k = 1;
                while (k * currCoin <= a) {
                    f[i][a] = Math.min(f[i][a],
                                       f[i][a - k * currCoin] + k);
                    k ++;
                }
            }
        }

        return f[coins.length][amount] <= amount ? f[coins.length][amount] : -1;
    }
}

Revelation:

• Init the f[i][amount != 0] = amount + 1, to avoid the integer overflow.

Java Solution:

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0 || amount == 0) {
            return 0;
        }

        // DP formula:
        // f[i][amount] = min(f[i - 1][amount],
        //                    f[i][amount - k*[i]] + k)
        long [][] f = new long [coins.length + 1][amount + 1];
        for (int i = 0; i <= coins.length; i ++) {
            for (int a = 0; a <= amount; a ++) {
                if (a == 0) {
                    f[i][a] = 0;
                } else {
                    f[i][a] = (long)Integer.MAX_VALUE;
                }
            }
        }

        for (int i = 1; i <= coins.length; i ++) {
            int currCoin = coins[i - 1];

            for (int a = 1; a <= amount; a ++) {
                f[i][a] = f[i - 1][a];
                int k = 1;
                while (k * currCoin <= a) {
                    f[i][a] = Math.min(f[i][a],
                                       f[i][a - k * currCoin] + k);
                    k ++;
                }
            }
        }

        return f[coins.length][amount] == Integer.MAX_VALUE ? -1 : (int)f[coins.length][amount];
    }
}

Revelation:

• If we use int[][] f = new int[...][...] there will be integer overflow, during the process, so here we just long type.