Knapsack
You know the 0/1 knapsack pattern. Now apply it to harder variants like Tallest Billboard, where constraints and state design push beyond textbook examples.
Lessons
1. Introduction to Knapsack
Why this family matters
2. What Knapsack DP Solves
Constraints that scream knapsack
3. When to Use Knapsack DP
Binary choices, additive limits
4. Problem - Tallest Billboard
LC 956 - equal height supports
5. Tallest Billboard - Why Naive Fails
Track difference, not both
6. Tallest Billboard - Defining the DP
Difference as the state dimension
7. Tallest Billboard - Transition
Skip, add left, or add right
8. Tallest Billboard - Base Cases
Both supports empty at start
9. Tallest Billboard - Implementation
Hash map for sparse states
10. Tallest Billboard - Time and Space
Why S not S² in the bound
11. Lessons from Tallest Billboard
One dimension beats two
12. Problem - Values You Can Make
CF 687C - subset of a subset
13. Values You Can Make - Why Naive Fails
Track two sums at once
14. Values You Can Make - Defining the DP
dp[total][partial] = reachable?
15. Values You Can Make - Transition
Include in total, partial, or skip
16. Values You Can Make - Base Cases
dp[0][0] = true, rest false
17. Values You Can Make - Implementation
Reverse iteration avoids reuse
18. Values You Can Make - Time and Space
Quadratic in target value
19. Lessons from Values You Can Make
Nested subset constraints
20. Problem - Profitable Schemes
LC 879 - the gang problem
21. Profitable Schemes - Why Naive Fails
Counting vs optimizing
22. Profitable Schemes - Defining the DP
Cap profit to bound states
23. Profitable Schemes - Core Logic
+= instead of max()
24. Profitable Schemes - Implementation
3D logic in 2D space
25. Lessons from Profitable Schemes
Counting with multiple constraints
26. Problem - Round Subset
CF 837D - maximize trailing zeros
27. Round Subset - Why Naive Fails
Zeros come from min(2s, 5s)
28. Round Subset - Defining the DP
Fix 5s, greedily pick 2s
29. Round Subset - Core Logic
Knapsack over factor counts
30. Round Subset - Implementation
Precompute 2s and 5s
31. Lessons from Round Subset
Optimize one, iterate the other
32. Problem - Fire
CF 864E - deadlines and values
33. Fire - Why Naive Fails
Sort by deadline first
34. Fire - Defining the DP
Time as the knapsack capacity
35. Fire - Core Logic
Must finish before deadline
36. Fire - Implementation
Reconstruction with backtracking
37. Lessons from Fire
Scheduling reduces to knapsack
38. Space Optimization - Why It Works
1D array suffices
39. Space Optimization - Implementation
Why backward for 0/1 knapsack
40. Bounded Knapsack - Problem Pattern
Each item has a copy limit
41. Reconstruction - Finding Selected Items
Which items made the optimal?
42. Reconstruction - Code Pattern
Backtrack through the DP table
43. Quiz: Pattern Recognition
Is this knapsack?
44. Quiz: Edge Cases
Zero capacity, empty arrays
45. Common Mistakes in Knapsack DP
Forward vs backward iteration
46. Problem - Number of Ways to Earn Points
LC 2585
47. Number of Ways to Earn Points - Implementation
Solution approach
48. Problem - Two Sets II
CSES 1093
49. Two Sets II - Implementation
Solution approach
50. Problem - Painting the Walls
LC 2742
51. Painting the Walls - Implementation
Solution approach
52. Problem - Number of Great Partitions
LC 2518
53. Number of Great Partitions - Implementation
Solution approach
54. Problem - Meet in the Middle
CSES 1628
55. Meet in the Middle - Implementation
Solution approach
56. Section Recap
From 0/1 to bounded to unbounded