Part VII · Dynamic Programming: Comprehensive Problem Families
43. Knapsack, Subset and Counting Dynamic Programming
6 lessons•28 topics•Intermediate / Advanced
0 of 6 lessons published
43.01Outline
Knapsack taxonomy
- 0/1 knapsack
- Unbounded knapsack
- Bounded knapsack
- Multiple-choice knapsack
- Value-based DP
43.02Outline
Subset sum family
- Subset sum
- Equal partition
- Minimum subset difference
- Target sum
- Count subset sums
43.03Outline
Coin change family
- Minimum coins
- Count combinations
- Count permutations
- Unlimited vs limited coins
- Order-sensitive transitions
43.04Outline
Counting sequences
- Count paths
- Compositions of n
- Staircase variants
- Catalan DP intro
- Tiling boards
43.05Outline
Partitioning problems
- Partition array for maximum sum
- Split into k groups
- Painting partition
- Rod cutting
43.06Outline
Space and transition optimizations
- One-dimensional knapsack
- Reverse iteration for 0/1
- Forward for unbounded
- Bitset subset-sum