Unbounded Knapsack
Same as 0/1 but an item may be reused, so the transition reads the current row instead of the previous one.
Dynamic ProgrammingO(n * W)New6 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
coin change
rod cutting
combination sum count
The template
Get this into muscle memory, then adapt the condition per problem.
for (const coin of coins)
for (let a = coin; a <= amount; a++)
dp[a] = Math.min(dp[a], dp[a - coin] + 1); Watch Coin ChangeIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Items can repeat, so taking one does not move the index forward.
- 2Loop order decides whether you count combinations or permutations.
- 3Coins outside, amount inside counts combinations.
Drill it
Every problem in the bank that uses this pattern.
0 / 6 solved