Related: Maximum Depth of Binary Tree Combination Sum
TARGET DECK: Leetcode FILE TAGS:
Intuition
- Greedy doesn’t work for this problem. Take the following scenario:
- coins = [1, 26, 50], amount = 99
- Greedy solution = 50 + 26 + 23 1’s = 25 coins
- Optimal solution = 26 + 26 + 26 + 21 1’s = 24 coins.
- coins = [1, 26, 50], amount = 99
- For the Top Down approach, be very careful about when you take or skip the current index.
- If you take, then be sure to + 1 that branch (if indeed it you reach 0 for your cur_amount, you will have the length of your branch. Otherwise, inf + 1 = inf still in the case where your cur_amount < 0 or your index is out of bounds).
- Additionally, in your DP array when memoizing, be sure to save the cur_amount and the index, since that is a unique identifier for the branch length at that point in time, and does not interfere with other branches that may find a different result, thereby giving the wrong dp answer.
- ex) 1, 1, 1, 1, 1 and 5 give the same result stored into dp.
- For Bottom Up, build up the amount from 1 to amount, saving each, since the later amounts closer to the amount depend on the computation of the previous amounts.
- ex) amount = 10, coins = [1, 2, 5] gave OPT(5) + OPT(1), in which OPT(5) was computed to be 1, then OPT(10) became OPT(5) + OPT(5), then OPT(11) became OPT(10) + OPT(1), so OPT(5) + OPT(5) + OPT(1).
Cards
START
Basic
Front: Coin Change - LeetCode
Back: 1 + opt[cur_amount - coin] for bottom up, wherein opt[cur_amount - cur_amount] initialized to 0.
END
Complexity
Runtime
For bottom up:
Space
For bottom up: since you store amount entries in dp array.
Code
Bottom Up
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
opt = [inf] * (amount + 1)
opt[0] = 0
for cur_amount in range(1, amount + 1):
for coin in coins:
if cur_amount - coin >= 0:
opt[cur_amount] = min(opt[cur_amount], 1 + opt[cur_amount - coin])
if opt[amount] == inf:
return -1
return opt[amount]Top Down
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
dp = {}
def r(cur_amount, i):
if (cur_amount, i) in dp:
return dp[(cur_amount, i)]
if i == n or cur_amount < 0:
return inf
if cur_amount == 0:
return 0
# Corrected: use a tuple (cur_amount, i) as the key in dp
take = inf
if cur_amount - coins[i] >= 0:
take = r(cur_amount - coins[i], i) + 1
skip = r(cur_amount, i + 1)
dp[(cur_amount, i)] = min(take, skip)
return dp[(cur_amount, i)]
res = r(amount, 0)
if res == inf:
return -1
return res