Examples / Dynamic programming▶Run in PyTrace
Dynamic Programming Visualization in Python
Dynamic programming solves a problem by combining the answers to smaller subproblems. In bottom-up DP you store those answers in a table, here dp[a] = the fewest coins that add up to a, and fill it from the smallest amount up.
For every amount a and every coin, if using that coin on top of the best answer for a - coin is better than what we have, we update dp[a]. Watching the array fill in makes the recurrence concrete.
ComplexityO(amount × len(coins)) time, O(amount) space.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [0] + [inf] * amount
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1
return dp[amount] if dp[amount] != inf else -1Inputs
coins[1,2,5]
amount11
expected3
What to watch
- The
dparray, withaanda - coinas pointers into it - Cells going from
inf(unreachable) to their final value - The comparison that decides whether a coin improves the answer