The Map of Dynamic Programming: A First-Principles Breakdown
The Real Problem: DP doesn't feel like one technique—it feels like a zoo of unrelated tricks. "Unique Paths" and "0/1 Knapsack" seem to have nothing in common. How do you learn something that appears endless?
Your Core Question (Designer's Brain)
You've identified the real problem: DP doesn't feel like one technique—it feels like a zoo of unrelated tricks.
The Truth: There aren't endless approaches. There are ~5-7 core thinking patterns that cover 95% of DP problems.
Where the Illusion Comes From
The appearance of "endlessness" comes from:
- Different state definitions (what are we tracking?)
- Different transition patterns (how do states relate?)
- Different optimization dimensions (what are we min/maxing?)
Once you understand these 5-7 patterns, you're not solving "300 different DP problems"—you're applying the same 5-7 patterns with small variations.
The Designer's Framework: What Makes Something "DP"?
The DP Recognition Property
A problem is DP-solvable when:
- Optimal substructure: Big solution built from smaller solutions
- Overlapping subproblems: Same small problems recalculated many times
- Decision at each step: Choose something, which affects future choices
Why These Three Matter
- Without #1: You can't build up solutions (need greedy/other approach)
- Without #2: Recursion is enough (no need for memoization)
- Without #3: It's just math, not optimization
The 5-7 Core DP Patterns (Your Learning Roadmap)
Pattern 1: Linear Sequence Decision
"At each position, make a choice based on previous positions"
Walking left-to-right, at each step looking backward.
State: dp[i] = "best answer ending at position i"
Examples:
- Climbing Stairs (1 or 2 steps)
- House Robber (rob or skip)
- Longest Increasing Subsequence
- Single index tracking position
- Decision affects what comes next
- Build solution by looking at previous positions
Learn from: 3-5 problems
Example Structure:
// Linear sequence pattern
for (int i = 0; i < n; i++) {
// Look back at previous positions
dp[i] = Math.max(
option1_from_dp[i-1],
option2_from_dp[i-2]
);
}
Pattern 2: Grid Traversal
"Moving through 2D space with constraints"
Can only build a cell from cells you've already visited.
State: dp[i][j] = "best answer reaching cell (i,j)"
Examples:
- Unique Paths
- Minimum Path Sum
- Dungeon Game
- Two indices (row, col)
- Transitions from top/left neighbors
- Building from top-left to bottom-right
Learn from: 3-4 problems
Example Structure:
// Grid traversal pattern
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dp[i][j] = something(
dp[i-1][j], // from top
dp[i][j-1] // from left
);
}
}
Pattern 3: Bounded Knapsack (Resource Allocation)
"Make choices under a constraint (weight/capacity/budget)"
"If I have X capacity left, and I'm considering item i, what's optimal?"
State: dp[i][w] = "best value using first i items with weight limit w"
Examples:
- 0/1 Knapsack
- Coin Change
- Partition Equal Subset Sum
- Two dimensions (items processed, resource remaining)
- Binary/multiple choice per item
- Resource constraint drives state
Learn from: 4-6 problems
Example Structure:
// Knapsack pattern
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
// Choice 1: Don't take item i
int skip = dp[i-1][w];
// Choice 2: Take item i (if it fits)
int take = 0;
if (weight[i] <= w) {
take = value[i] + dp[i-1][w - weight[i]];
}
dp[i][w] = Math.max(skip, take);
}
}
Pattern 4: Interval DP
"Problems on subarrays/substrings where you merge solutions"
"What's the answer for substring [i...j]? Try splitting it at every k."
State: dp[i][j] = "best answer for range i to j"
Examples:
- Longest Palindromic Substring
- Burst Balloons
- Matrix Chain Multiplication
- Length-based building (solve small intervals first)
- Transitions try all split points
- Build from smaller ranges to larger ranges
Learn from: 3-5 problems
Example Structure:
// Interval DP pattern
// Build by increasing length
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
// Try all split points
for (int k = i; k < j; k++) {
dp[i][j] = Math.max(
dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, j)
);
}
}
}
Pattern 5: State Machine DP
"You're in different 'modes' and transitions between modes have costs"
"At each step, what state am I in? What states can I transition to?"
State: dp[i][state] = "best answer at position i in this state"
Examples:
- Best Time to Buy/Sell Stock (holding vs not holding)
- Paint House (last color used)
- Dice Roll Simulation (last number rolled, consecutive count)
- Multiple states at each position
- Transitions between states with rules
- Current state limits future choices
Learn from: 3-4 problems
Example Structure:
// State machine pattern
enum State { HOLDING, NOT_HOLDING }
for (int i = 0; i < n; i++) {
// Transition: buy stock
dp[i][HOLDING] = Math.max(
dp[i-1][HOLDING], // already holding
dp[i-1][NOT_HOLDING] - price[i] // buy today
);
// Transition: sell stock
dp[i][NOT_HOLDING] = Math.max(
dp[i-1][NOT_HOLDING], // already not holding
dp[i-1][HOLDING] + price[i] // sell today
);
}
Pattern 6: DP on Trees
"Decisions propagate up/down a tree structure"
"What's the answer for this subtree? Combine children's answers."
State: dp[node] = "best answer for subtree rooted at node"
Examples:
- House Robber III (rob houses in tree)
- Binary Tree Maximum Path Sum
- Tree Diameter
- Recursive tree traversal
- Combine answers from children
- Post-order processing
Learn from: 2-3 problems
Example Structure:
// Tree DP pattern
public int treeDP(TreeNode node) {
if (node == null) return 0;
// Get answers from subtrees
int left = treeDP(node.left);
int right = treeDP(node.right);
// Combine for current node
return combine(node.val, left, right);
}
Pattern 7: Digit/Bitmask DP (Advanced)
"State includes which subset/digits used"
Encode complex state in bits/digits.
State: dp[mask] = "answer when subset 'mask' is used"
Examples:
- Traveling Salesman
- Number of Dice Rolls With Target Sum
This pattern is advanced and can be skipped initially. Learn it after mastering patterns 1-6.
Learn from: 2-3 problems
Your Learning Path: The Numbers
- Total patterns: 5-7 (depending on if you count advanced)
- Problems per pattern: 3-5
- Your curriculum: 20-30 problems total covers all essential DP patterns
Why This Works
| Pattern Group | Problems | Coverage |
|---|---|---|
| Patterns 1-5 (Core) | ~20 problems | Solid foundation |
| Pattern 6 (Nice to have) | +3 problems | 95% coverage |
| Pattern 7 (Advanced) | +3 problems | Learn later if needed |
After 20-30 problems: You'll recognize "this is Pattern 3 with a twist" instead of "this is completely new."
The Meta-Process: How to Study Each Pattern
Step 1: Struggle First
Do 1 easy problem "naked" (no solution): Struggle is learning
Step 2: Study the State Definition
Study the solution's STATE DEFINITION: Why track THIS, not something else?
Step 3: Apply It Yourself
Do 2 more problems in pattern: Apply the state definition yourself
Step 4: Ask Boundary Questions
- What if constraints change? (2D → 3D grid?)
- What if optimization flips? (min → max?)
- Can I solve it bottom-up? Top-down? Why does one feel natural?
Why Unique Paths ≠ Knapsack (But They're Not Unrelated)
Unique Paths (Pattern 2)
State = position (i, j)
Transition = came from (i-1, j) or (i, j-1)
No "choice" (both paths contribute - ADDITION)
Knapsack (Pattern 3)
State = (items considered, weight left)
Transition = take item or skip it
Choice matters (max of two options - SELECTION)
What's the SAME (Meta-Level)?
- Both have 2D state space
- Both build bigger solutions from smaller
- Both eliminate recalculation via memoization
The difference: Unique Paths = counting (additive), Knapsack = optimizing (choice).
Your Action Plan
Phase 1 (Week 1-2): Learn Pattern 1, 2, 3
- Do 10-12 problems
- These are most common
Phase 2 (Week 3): Learn Pattern 4, 5
- Do 6-8 problems
- Handle 90% of DP problems now
Phase 3 (Week 4): Learn Pattern 6, Review
- Do 3-4 problems
- Solidify by seeing connections
Total time: 4 weeks, 20-30 problems = DP mastery
The Insight That Makes This "Obvious"
Every DP problem is answering:
- "What's my state?" (What am I tracking?)
- "What's my transition?" (How do states connect?)
- "What's my base case?" (Where do I start?)
The patterns just categorize common answers to these questions.
Once you see the pattern, you're not solving "Unique Paths" vs "Knapsack"—you're applying Pattern 2 vs Pattern 3.
That's when DP stops feeling like magic and starts feeling like a toolbox.
Pattern Recognition Cheat Sheet
| Keywords/Clues | Most Likely Pattern | Key State |
|---|---|---|
| "at each position", "sequence", "previous" | Pattern 1: Linear | dp[i] |
| "grid", "paths", "reach (i,j)" | Pattern 2: Grid | dp[i][j] |
| "capacity", "budget", "weight limit", "select items" | Pattern 3: Knapsack | dp[i][w] |
| "substring", "subarray", "range [i,j]" | Pattern 4: Interval | dp[i][j] |
| "states", "mode", "holding", "color" | Pattern 5: State Machine | dp[i][state] |
| "tree", "subtree", "root" | Pattern 6: Tree DP | dp[node] |
| "subset", "visited", "bitmask" | Pattern 7: Bitmask | dp[mask] |
Final Thoughts
This map gives you the structure to navigate DP problems.
But the real learning happens when you:
- Struggle with problems
- Discover why a state definition works
- Connect patterns across problems
- Build your own intuition
The map shows you where to go. The journey builds the skill.
Next Steps
- Read this document to understand the landscape
- Pick Pattern 1 (Linear Sequence Decision)
- Do 3 problems following the meta-process
- Move to Pattern 2, repeat
- After 5 patterns, you'll see the connections
Recommended order: Pattern 1 → 2 → 3 → 5 → 4 → 6 → 7