Related: Knapsack
Danger
Wasn’t able to solve this problem bottom up, which relies on Knapsack unbounded. I got kind of close, but this is not solvable via 1D dynamic programming. It is important to understand why.
Intuition
Complexity
Runtime
Space
Code
Bottom Up
Top Down
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
dp = {}
def r(i, cur_amount):
if (i, cur_amount) in dp:
return dp[(i, cur_amount)]
if cur_amount == 0:
return 1
if i == n or cur_amount < 0:
return 0
r1 = r(i, cur_amount - coins[i])
r2 = r(i + 1, cur_amount)
dp[(i, cur_amount)] = r1 + r2
return dp[(i, cur_amount)]
return r(0, amount)