Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Coin Combinations.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Unbounded knapsack combinations matches the clues
- 2Keep this true after every move: after a coin type, dp[amount] counts combinations using only processed coin types
- 3Reach the result within O(amount times coin count) time and O(amount) space
Rules and pressure
- Target cost: O(amount times coin count) time and O(amount) space
- State rule: after a coin type, dp[amount] counts combinations using only processed coin types
Lesson 1 of 3
Live algorithm trace
Unbounded knapsack combinations
Complete execution1 of 5
1
2
5
0
amount
1
2
Seed amount zero with one empty combination.
1
dp[0] = 12
for each coin type3
for amount from coin through target4
extend combinations at amount - coin5
dp[amount] += dp[amount - coin]6
return dp[target]target = 5dp = [1,0,0,0,0,0]
Truth to preserve / Cost target
Truth to preserve
after a coin type, dp[amount] counts combinations using only processed coin types
Cost target
O(amount times coin count) time and O(amount) space
Process coin types outside and amounts inside. This order lets each combination appear once, regardless of the order its coins could be listed.
Your call · What should guide every step of this algorithm?