Knapsack, LCS, DP

89 topics across 5 chapters

Chapter 1

DP Foundations

Recursion → Memoization → Tabulation

3 subtopics

Implement memoization for a small recurrence (e.g., Fibonacci / grid paths)

Convert a memoized solution to tabulation (bottom-up)

Create a checklist for base cases and invalid states

Overlapping Subproblems & Optimal Substructure

2 subtopics

Recognize overlapping subproblems from repeated parameters

Write a short proof/argument for optimal substructure on a DP problem

State, Transition, Base Cases (DP Formulation)

3 subtopics

Define state variables precisely (what each index means)

Derive the transition (min/max/or count) from smaller states

Set base cases and handle boundaries cleanly (0 rows/cols, empty sets)

DP Complexity Analysis (Time & Memory)

2 subtopics

Compute time as (#states) × (work per transition)

Estimate memory usage and fit it to constraints

Chapter 2

Core DP Patterns & Techniques

↗ State, Transition, Base Cases (DP Formulation) (see Chapter 1)

Iteration Order & Dependency Management

3 subtopics

Determine correct loop ordering from dependency direction

Draw the dependency graph / DP grid arrows for a sample DP

Prevent uninitialized reads (fill order, sentinel values)

Space Optimization (Rolling Arrays, Bitsets)

3 subtopics

Apply rolling arrays to compress 2D → 1D when valid

Use bitset DP for subset sum when weights are moderate

Know when space optimization breaks reconstruction unless you store decisions

Reconstructing an Optimal Solution (Backtracking)

3 subtopics

Store decisions/parent pointers for reconstruction

Backtrack from the DP table to build the chosen solution

Handle ties (multiple optimal answers) with consistent tie-breaking

Subset / Bitmask DP (Intro Pattern)

2 subtopics

Write a basic bitmask DP over subsets (mask → mask without one element)

Compare bitmask DP vs meet-in-the-middle by constraints

Chapter 3

Knapsack Family (0/1, Unbounded, Variants)

↗ State, Transition, Base Cases (DP Formulation) (see Chapter 1)

Modeling Knapsack Problems as DP

3 subtopics

Choose DP dimensions for knapsack (item index, weight, value)

Pick the best formulation: weight-based DP vs value-based DP

Translate a story constraint into a recurrence (take/skip, bounded/unbounded)

0/1 Knapsack (Max Value)

3 subtopics

Implement classic 0/1 knapsack with 2D DP (items × capacity)

Optimize 0/1 knapsack to 1D DP (iterate weight descending)

Recover selected items for 0/1 knapsack on a small example

Subset Sum / Partition DP (Boolean & Counting)

3 subtopics

Implement subset sum boolean DP (reachable sums)

Solve equal-partition (split array into two equal-sum sets)

Count subsets / count partitions (DP counting) and avoid overflow

Unbounded Knapsack / Coin Change

3 subtopics

Write unbounded knapsack recurrence (iterate weight ascending)

Coin change: minimum coins to reach amount (min DP)

Coin change: number of ways (combinations vs permutations)

Advanced Knapsack Variants & Constraint Tricks

3 subtopics

Solve a 2-constraint knapsack (e.g., weight and volume)

Handle huge capacity via value-based DP (min weight for each value)

Bounded knapsack via binary splitting / power-of-two decomposition

↗ Reconstructing an Optimal Solution (Backtracking) (see Chapter 2)

Chapter 4

LCS & Sequence DP (LCS, Edit Distance, Variants)

↗ State, Transition, Base Cases (DP Formulation) (see Chapter 1)

LCS DP Recurrence & Table Filling

3 subtopics

Implement LCS length DP recurrence (match vs max of neighbors)

Indexing practice: 1-based DP table with 0 row/col for empty prefixes

Understand LCS complexity and when O(n·m) is too big

Reconstructing One LCS

2 subtopics

↗ Reconstructing an Optimal Solution (Backtracking) (see Chapter 2)

Reconstruct an LCS by walking the DP table (without extra parent pointers)

LCS-Adjacent Variants (LCSubstring, Edit Distance, SCS)

3 subtopics

Longest Common Substring DP (reset to 0 on mismatch)

Edit Distance (Levenshtein) DP (insert/delete/replace)

Shortest Common Supersequence via LCS/DP relationship

↗ Space Optimization (Rolling Arrays, Bitsets) (see Chapter 2)

Hirschberg’s Algorithm (LCS in Linear Space)

3 subtopics

Learn Hirschberg’s idea: divide-and-conquer using middle row scores

Decide when Hirschberg helps (memory bound, still O(n·m) time)

Implement Hirschberg for one LCS on a small test case

Sequence DP Connections (LIS & 2-Index Patterns)

3 subtopics

Implement LIS with O(n^2) DP and compare to LCS-style transitions

Practice 2-index DP patterns (i,j) on sequences/strings

Map problems to patterns: LCS vs LIS vs edit distance vs knapsack

Chapter 5

Practice & Implementation Workflow

Coding Templates (Top-Down & Bottom-Up)

3 subtopics

Write a reusable top-down DP template (cache + recursion)

Write a reusable bottom-up DP template (table + loop order)

Choose good sentinel values and handle unreachable states robustly

Debugging & Pitfalls in DP

3 subtopics

Design tiny test cases that cover boundaries and transitions

Print DP tables (or key slices) and verify invariants during debugging

Use an off-by-one checklist for arrays/strings (prefix lengths vs indices)

Practice Progression (Problem Ladder)

3 subtopics

Solve a 10-problem ladder: 0/1 knapsack → subset sum → coin change → LCS → edit distance

Do timed practice and write a postmortem (state choice, transitions, bugs)

Maintain a personal “DP patterns notebook” with templates and pitfalls

Choosing the Right DP Approach Under Constraints

3 subtopics

Recognize DP candidates: choices + constraints + overlapping subproblems

Use constraints to pick an approach (O(nW), O(nm), value-DP, bitset, Hirschberg)

Optimize only after correctness (then reduce memory/time systematically)