DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)

Back to Dynamic Programming

Making Change Visualizer

Watch bottom-up DP find the minimum number of coins for any target amount, building from amount 0 upward.

Time: O(amount × coins)

Space: O(amount)

Bottom-up DP

Unbounded Knapsack

Target Amount: 11

Available Coins (comma-separated)

Animation Speed: 1000ms

Fast (300ms)Slow (2000ms)

Step 1 of 0Phase: start

Available Coins

DP Table — Minimum Coins per Amount

dp[0]

∞

dp[1]

∞

dp[2]

∞

dp[3]

∞

dp[4]

∞

dp[5]

∞

dp[6]

∞

dp[7]

∞

dp[8]

∞

dp[9]

∞

dp[10]

∞

dp[11]

∞

Current Step

Click Play to begin

Algorithm Details

Time:O(amount × coins)

Space:O(amount)

Type:Bottom-up DP

Pattern:Unbounded Knapsack

Key DP Concepts

Optimal Substructure: optimal solution for i uses optimal for i−coin
Recurrence: dp[i] = min(dp[i], dp[i−coin]+1)
Base Case: dp[0] = 0
Sentinel: ∞ means "impossible so far"

Knowledge Check

Question 1 of 3