Dynamic ProgrammingIntermediate
Unbounded Knapsack
Like 0/1 Knapsack, but each item can be used unlimited times.
Problem: Coin Change (Unbounded Knapsack)
Coins: [1, 3, 4], Amount: 6. Find minimum number of coins to make the amount.
0
∞
∞
∞
∞
∞
∞
Initialize dp array
dp[0] = 0 (0 coins needed for amount 0). All other dp[i] = ∞ (impossible initially). We'll fill each cell with the minimum coins needed.
Step 1/8
Speed:
When to Use
- Unlimited supply of items
- Coin change problem
- Rod cutting
- Minimum coins to make amount
Key Indicators
- Unlimited item usage
- Coin change
- Ways to make a target
- Minimum items for target
Complexity
Time
O(n × W)
Space
O(W)
Common Problems
Coin ChangeCoin Change IIRod CuttingPerfect Squares
Code
dp = [inf] * (amount + 1)
dp[0] = 0
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)