322. Coin Change

Coin Change - LeetCodeLeetCode

brute force

recursive like a tree, then do BFS, find the level which can subtract to 0 (11 -1 - 5 - 5 = 0

time: O(n^k), k is coins type

DFS + memo (top down)

T: O(kn)

S: O(n)

class Solution {
    public int coinChange(int[] coins, int amount) {
        return dfs(coins, amount, new Integer[amount+1]);
    }
    private int dfs(int[] coins, int amount, Integer[] memo) {
        if (amount == 0) { // no more amount, should return 0
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            int numbers = dfs(coins, amount - coin, memo);
            if (numbers == -1) {
                continue;
            }
            result = Math.min(result, 1 + numbers);
        }
        return memo[amount] = (result == Integer.MAX_VALUE ? -1 : result);
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        return dp(coins, amount, new Integer[amount+1]);
    }
    private int dp(int[] coins, int amount, Integer[] memo) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }
        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dp(coins, amount - coin, memo);
            if (sub == -1) { // key point!
                continue;
            }
            result = Math.min(result, sub + 1);
        }
        return memo[amount] = (result != Integer.MAX_VALUE ? result: -1);
    }
    
}

// thought -> 
/*
fewest number of coins
subproblem -> f(10), f(9), f(6) , these are all dependent
f(11) = f(10) + 1 (if choose 1)
f(11) = f(9) + 1 (if choose 2)
f(11) = f(6) + 1 (if choose 5)

   f(11)
   /    
   f(10)  9.  6
   / \\    /
   9 8 5  8
   
k : how many kind of coins type
k^n , n subproblems
*/

// use memo -> k^n to k*n

   
   

DP (bottom up

有幾種硬幣, 組成 amount => 是不是很像爬樓梯問題

subproblem & dp array:

f(n) = min ( f(n-k) ), for k in [1,2,3]) + 1

time: O(kn), n: amount, k: coins' number, O(n)

space: O(n), n: amount

class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount+1]; // 初始結果都是amount+1
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for (int i = 0; i < amount+1; 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 : dp[amount]; 
        // 初始amount+1,所以如果比 amount 大, 代表沒找到
    }
}

當前填滿容量 dp[i] 最少需要的硬幣 =

min(之前填滿容量 dp[i] 最少需要的硬幣 , 填滿容量 dp[i - coin 需要的硬幣 + 1個當前硬幣] . ）

for loop 去變換 coin 需要的硬幣, f(n) = min ( f(n-k) ), for k in [1,2,3]) + 1

因為是多個 f(n-k) 要找最小,

所以在 dp[i] 取得值, 要 Math.min(dp[i], dp[i-coins[j]+1)

Math.min(dp[i] . => 代表之前 Math.min(dp[i], dp[i-coins[j]+1) => dp[i-coins[j]+1算出的結果

        for (int i = 0; i < amount+1; 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);
                }
            }
        }

new version

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);
        
        dp[0] = 0;
        
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}