Dynamic Programming
Curriculum
Master optimization through overlapping subproblems, optimal substructure, and systematic state-space exploration.
What This Category Is Really About
Same subproblems solved repeatedly. Cache results to avoid recomputation. Memoization (top-down) or tabulation (bottom-up).
Optimal solution built from optimal solutions to subproblems. Local optimality leads to global optimality.
Define state that captures subproblem. State transitions define recurrence relation. DP table stores computed states.
Express solution in terms of smaller subproblems. Base cases terminate recursion. Transitions define computation order.
Mental Model & Invariants
DP is recursion with memory—avoid recomputing by caching.
"Break problem into subproblems. If subproblems overlap, cache results. If optimal substructure exists, combine cached solutions optimally."
Break this, and you either recompute or get wrong answers.
Memoization
Top-down: write recursive solution, add cache. Compute on demand. Natural for thinking recursively.
Tabulation
Bottom-up: fill table iteratively. Compute in dependency order. Often more space-efficient.
Space Optimization
Often only need previous row/column. Reduce O(n²) space to O(n). Sliding window over DP table.
Think in States
Define state that captures subproblem. Identify state transitions. Write recurrence relation. Choose memoization or tabulation.
When to Think "Dynamic Programming"
sensorsStrong Signals
Optimization problem (min/max/count)
Overlapping subproblems visible
Choices at each step
Optimal substructure present
Exponential brute force
"How many ways" questions
ruleProblem Patterns
Sequence/string problems
Grid path problems
Knapsack variants
Partition problems
Core Patterns You Must Master
Linear DP
1D array. Each state depends on previous states. Climbing stairs, house robber, decode ways.
dp[i] computed from dp[i-1], dp[i-2], etc.
2D Grid DP
2D table. State depends on adjacent cells. Unique paths, minimum path sum, edit distance.
dp[i][j] from dp[i-1][j], dp[i][j-1], dp[i-1][j-1].
Knapsack
0/1 knapsack, unbounded knapsack, subset sum. Include/exclude decisions.
dp[i][w] = max(include item i, exclude item i).
String DP
Longest common subsequence, palindrome problems, edit distance. Character matching.
Match characters or skip. Build from smaller strings.
Tree DP
DP on tree structures. House robber III, binary tree cameras. Subtree solutions.
Combine solutions from left and right subtrees.
State Compression
Bitmask DP for small state spaces. Traveling salesman, subset enumeration.
State represented as bitmask. Transitions flip bits.
How to Learn This Category
Master Fibonacci Pattern
Start with climbing stairs. Understand how dp[i] depends on previous states. Practice writing recurrence relations.
Learn Memoization First
Write recursive solution. Add cache (hashmap/array). Understand top-down approach before bottom-up.
Practice State Definition
What does dp[i] or dp[i][j] represent? Clear state definition is critical. Write it down explicitly.
Draw the DP Table
Visualize how table fills. Understand dependency order. See patterns in how values propagate.
Convert to Tabulation
Take memoized solution, convert to bottom-up. Understand iteration order. Practice both approaches.
Optimize Space
Identify if only previous row/column needed. Reduce space from O(n²) to O(n). Use rolling arrays.
Canonical Problem List
auto_awesome_motionFoundation
Climbing Stairs
Classic Fibonacci DP. Each step depends on previous two.
House Robber
Linear DP with skip constraint. Rob or skip each house.
Maximum Subarray
Kadane's algorithm. Track max ending at current position.
Coin Change
Unbounded knapsack. Minimum coins to make amount.
Unique Paths
2D grid DP. Count paths from top-left to bottom-right.
auto_awesome_motionIntermediate
Longest Increasing Subsequence
O(n²) DP or O(n log n) with binary search.
Longest Common Subsequence
2D string DP. Match or skip characters.
Edit Distance
String transformation. Insert, delete, replace operations.
Partition Equal Subset Sum
0/1 knapsack variant. Can partition into equal sums?
Decode Ways
Count ways to decode string. Linear DP with constraints.
Word Break
Can segment string using dictionary? DP with string matching.
auto_awesome_motionAdvanced
Regular Expression Matching
2D DP with wildcards. Complex state transitions.
Burst Balloons
Interval DP. Choose last balloon to burst.
Longest Palindromic Subsequence
2D DP on palindromes. Build from smaller substrings.
Distinct Subsequences
Count distinct subsequences. 2D string DP.
Common Mistakes
Unclear State Definition
Don't know what dp[i] represents. Leads to wrong recurrence relation.
Write explicit state definition before coding. What does each dimension represent?
Wrong Base Cases
Incorrect initialization. DP table starts with wrong values.
Identify base cases from problem. Initialize dp table correctly before filling.
Incorrect Iteration Order
Computing dp[i] before dependencies available. Results in wrong values.
Understand dependency graph. Iterate in order that ensures dependencies computed first.
Not Considering All Transitions
Missing state transitions. Optimal solution not explored.
For each state, consider all possible previous states. Enumerate all transitions.
Forgetting to Cache in Memoization
Recomputing same subproblems. No speedup over brute force.
Check cache before computing. Store result after computing. Return cached value if exists.
Interview Guidance
What they test
- →State definition clarity
- →Recurrence relation correctness
- →Base case identification
- →Memoization vs tabulation choice
Strategy
Start with brute force recursive solution. Identify overlapping subproblems. Define state clearly. Write recurrence relation. Add memoization or build table bottom-up.
The Verbal Template
"dp[i] represents [what]. dp[i][j] represents [what for dimensions i and j]."
"dp[i] = [function of previous states]. This captures [why this transition is correct]."
"When [condition], dp value is [base value]. This handles [edge case]."
"Time: O([states] × [transitions per state]). Space: O([DP table size])."
When You've Mastered It
Define state clearly and quickly
Write recurrence relations correctly
Identify overlapping subproblems
Choose memoization vs tabulation
Optimize space when possible
Recognize DP patterns instantly
What This Unlocks Next
Advanced DP Patterns
Digit DP, probability DP, DP on trees, bitmask DP. Complex state spaces and transitions.
DP Optimizations
Convex hull trick, divide and conquer optimization, monotonic queue optimization. Reduce complexity.
Game Theory
Minimax, alpha-beta pruning, Nim games. DP for optimal strategies in adversarial settings.
Computational Geometry
Closest pair, convex hull, line sweep. DP for geometric optimization problems.