Dynamic ProgrammingIntermediate
0/1 Knapsack
Choose items (take or skip each) to maximize value within a capacity constraint.
Problem: Partition Equal Subset Sum
Can we partition [1, 5, 11, 5] into two subsets with equal sum? (Sum = 22, Target = 11)
Input Array
1
5
11
5
DP Array (can we make sum i?)
T
F
F
F
F
F
F
F
F
F
F
F
Index represents target sumT = achievable, F = not achievable
Initialize: dp[0] = true
Target sum = 11. Create DP array of size 12. dp[i] = can we make sum i? Start with dp[0] = true (sum 0 with no items).
Step 1/8
Speed:
When to Use
- Select subset with weight/capacity constraint
- Maximize/minimize value with constraints
- Partition into two equal subsets
Key Indicators
- Take or skip each item
- Capacity constraint
- Subset with target sum
- Partition problem
Complexity
Time
O(n × W)
Space
O(W) with space optimization
Common Problems
0/1 KnapsackPartition Equal Subset SumTarget SumLast Stone Weight II
Code
dp = [0] * (capacity + 1)
for item in items:
for w in range(capacity, item.weight - 1, -1):
dp[w] = max(dp[w], dp[w - item.weight] + item.value)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)