518. Coin Change 2 (Unbounded Knapsack problem)

https://labuladong.github.io/algo/3/27/83/

https://labuladong.github.io/algo/3/27/83/

DFS

https://leetcode-cn.com/problems/coin-change-2/solution/custerxue-xi-bi-ji-dfs-dp-by-custergo/

class Solution {
    public int change(int amount, int[] coins) {
        return dfs(amount, coins, 0);
    }
    private int dfs(int amount, int[] coins, int start) {
        if (amount == 0) { // get one way to fit amount
            return 1;
        }
        if (amount < 0) { // no way to fit amount
            return 0;
        }
        int result = 0;
        // next round from next start to take coin deno
        for (int i = start; i < coins.length; i++) { // notice start, use differnet coins to ...
            result += dfs(amount - coins[i], coins, i);
        }
        return result;
    }
}

DFS + memo

class Solution {
    public int change(int amount, int[] coins) {
        Integer[][] memo = new Integer[amount+1][coins.length];
        return dfs(amount, coins, 0, memo);
    }
    private int dfs(int amount, int[] coins, int start, Integer[][] memo) {
        if (amount == 0) { // key point is here!
            return 1;
        }
        if (amount < 0) { // key point is here!
            return 0;
        }
        if (memo[amount][start] != null) {
            return memo[amount][start];
        }
        int result = 0;
        for (int i = start; i < coins.length; i++) {
            result += dfs(amount - coins[i], coins, i, memo);
        }
        memo[amount][start] = result;
        return memo[amount][start];
    }
}

上個做法用了 combination 的想法 i = start

也可以這樣做, 這樣做就跟完全背包的概念一樣

class Solution {
    public int change(int amount, int[] coins) {
        Integer[][] memo = new Integer[amount+1][coins.length];
        return dfs(amount, coins, 0, memo);
    }
    private int dfs(int amount, int[] coins, int start, Integer[][] memo) {
        if (amount == 0) { // key point is here!
            return 1;
        }
        if (amount < 0) { // key point is here!
            return 0;
        }
        if (start == coins.length) {
            return 0;
        }
        if (memo[amount][start] != null) {
            return memo[amount][start];
        }
        int result = 0;
        
        result += dfs(amount - coins[start], coins, start, memo) // 選 coin
                    + dfs(amount, coins, start+1, memo); // 不選 coin
        
        memo[amount][start] = result;
        return memo[amount][start];
    }
}

start + 1 也可以避開重複使用 coin 的 case

因為我們要的結果是 solutions, 我們要的是 combination, 所以 要避免重複用 1 (以下面的例子來說）

DP - 2D - Unbounded Knapsack problem

class Solution {
    public int change(int amount, int[] coins) {
        int m = coins.length;
        int n = amount;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j - coins[i-1] >= 0) {
                    dp[i][j] = dp[i-1][j]  // not choose
                        + dp[i][j - coins[i-1]]; // choose
                } else {
                    dp[i][j] = dp[i-1][j]; // j - coins[i-1], not choose
                }
            }
        }
        return dp[m][n];
    }
}
/*
so use knapsack problem - Unbounded Knapsack problem
choose
or not choose

dp[m][n]: m coins make number of combinations that make up that amount(n), infinite number of each kind of coin
so it'a Unbounded Knapsack problem

m item put into n (weight), m is Unbounded

init case : dp[i][0] = 1;

                if (j - coins[i-1] >= 0) {
                    dp[i][j] = dp[i-1][j]  // not choose
                        + dp[i][j - coins[i-1]]; // choose
                } else {
                    dp[i][j] = dp[i-1][j]; // j - coins[i-1], not choose
                }
TC: O(mn)
SC:O(mn)
*/

DP - space 優化到 O(n)

因為dp 数组的转移只和 dp[i][..] 和 dp[i-1][..] 有关, i 和 i -1

from 2D to 1D, 去掉 i 的部分

class Solution {
    public int change(int amount, int[] coins) {
        int m = coins.length;
        int n = amount;
        int[] dp = new int[n+1];
        dp[0] = 1;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j - coins[i-1] >= 0) {
                    dp[j] = dp[j]  // not choose
                        + dp[j - coins[i-1]]; // choose
                }
            }
        }
        return dp[n];
    }
}

for (int coin : coins) loop 外什麼一定要寫在外層 loop呢？ 為了 排列唯一

那因為 coin 只是遍例, 所以用 for (int coin : coins) 就可以了

dp 部分也可以改成 +=

time: O(coin * amount)

space: O(amount)

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1; // when amount = 0, there is 1 combination
        for (int coin : coins) { // notice coins for loop must be in out loop
            for (int i = coin; i <= amount; i++) { // from coin so dont need i >= coin if statement
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
/*
dp[i]: the number of combinations that make up that amount i.

when choose c from coins[]
dp[i] += dp[i-c]

注意：
for (int coin : coins) { // notice coins for loop must be in out loop
確保整個排列是唯一的方式: coin 在外層 loop
因為 coin 是照順序去組合的, 所以 coins[1, 3, 5]

一定是先做完 1 的排列, 才做3 

也就是組合 amount=4, 只會出現, 1,3 , 不會出現 3 1 的組合
*/