Core pattern
Knapsack DP
Step 6 of 14Pattern 4 of 7
×How to recognize it fast
Whenever the problem is about choosing numbers under a target, sum, or capacity, knapsack is usually close by.
When you see
subset sumpartition equaltarget amountchoose itemscapacityminimum coinsnumber of combinations
Think
- For each item, do I take it or skip it?
- What does dp[x] mean for a target sum or capacity x?
What to do once the pattern is clear
Core trick
- Define dp[x] as best, count, or possible for total x.
- Choose the correct transition for take versus skip.
- The loop direction matters more than most students realize.
Shortcut recognition
Numbers plus target plus subset choiceCan we reach a target?How many ways can we build a sum?
Hidden trick
0/1 knapsack loops backward because each item can be used once. Unbounded knapsack loops forward because reuse is allowed. That single detail fixes a huge number of DP mistakes.
Typical 0/1 recurrence
dp[x] = max(dp[x], value + dp[x - weight])