Coin Change

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

# Solution

Both solutions take O(len(coins)amount)O(len(\text{coins}) * \text{amount}) time and O(amount)O(\text{amount}) space.

# Recursive DP - Top down (TLE)

def coinChange(self, coins: List[int], amount: int) -> int:
    res = [sys.maxsize for _ in range(amount+1)]

    def dfs(i):
        if i == 0:
            return 0
        if i < 0:
            return -1
        if res[i] != sys.maxsize:
            return res[i]
        min_val = sys.maxsize
        for coin in coins:
            temp = dfs(i-coin)
            if temp >= 0:
                min_val = min(1 + temp, min_val)
        if min_val == sys.maxsize:
            return -1
        res[i] = min_val
        return res[i]
    return dfs(amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Iterative DP - Bottom up

def coinChange(self, coins: List[int], amount: int) -> int:
    res = [sys.maxsize for _ in range(amount+1)]
    res[0] = 0
    for i in range(1, amount+1):
        for coin in coins:
            if i - coin < 0:
                continue
            res[i] = min(res[i], 1 + res[i-coin])
    if res[-1] == sys.maxsize:
        return -1
    return res[-1]
1
2
3
4
5
6
7
8
9
10
11