322. Coin Change

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

Python

Bottom-up DP

• Time: O(amount * C)
• Space: O(amount)

coin\amount	0	1	2	3	4	5	6	7	8	9	10	11
1	0	1	2	3	4	5	6	7	8	9	10	11
5	0	1	2	3	4	1	2	3	4	5	2	3
6	0	1	2	3	4	1	1	2	3	4	2	2
8	0	1	2	3	4	1	1	2	1	2	2	2

歸納此表得知，某個cell的value來自：pre_row[col - amount] + 1

詳解參考：https://www.youtube.com/watch?v=Y0ZqKpToTic

from math import inf


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        mapper = [inf] * (amount+1)

        mapper[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i >= coin:
                    mapper[i] = min(mapper[i], mapper[i-coin]+1)

        if mapper[amount] == inf:
            return -1

        return mapper[amount]

Top-down DP

from math import inf


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount < 1:
            return 0

        dp = [0]*(amount+1)

        def dfs(remains):
            if remains < 0:
                return -1
            if remains == 0:
                return 0

            nonlocal dp

            if dp[remains] != 0:
                return dp[remains]

            cur_min = inf
            for coin in coins:
                result = dfs(remains-coin)
                if result >= 0 and result < cur_min:
                    cur_min = 1 + result
            dp[remains] = -1 if cur_min == inf else cur_min

            return dp[remains]

        return dfs(amount)

Javascript

var coinChange = function(coins, amount) {
    const dp = [0];
    for (let i = 1; i <= amount; i++) {
      let tmp = Infinity;
      for (const coin of coins) {
        const remain = i - coin;
        if (remain >= 0 && dp[remain] >= 0) {
          tmp = Math.min(dp[remain] + 1, tmp);
        }
      }
      dp[i] = tmp === Infinity ? -1 : tmp;
    }
    return dp[amount]
};