PATTERN 13: Dynamic Programming (DP)
D
Qubits of DPK
April 11, 2026
Core DSA
Pattern 13 is the boss level — but if you approach it correctly, it becomes systematic, not scary.
Remember this:
DP is not a topic. It’s disciplined recursion.
Core Idea (lock this sentence)
“Avoid solving the same subproblem more than once.”
Every DP problem starts as:
- Recursion → repeated work → memoization → tabulation → 1D Tabilation if possible
If you skip recursion understanding, DP will feel like memorization.
How to Recognise This Pattern (CRITICAL)
Think DP when:
- There are overlapping subproblems
- You’re asked for maximum / minimum / count
- A greedy choice fails
- Constraints hint O(N²) → O(N)
If recursion tree repeats → DP.
30 MUST-DO INTERVIEW PROBLEMS
(10 Easy → 10 Medium → 10 Hard)
EASY : DP Basics (1D)
Goal: understand state definition.
- #Tribonacci Number – LC 1137
- #House Robber – LC 198
- #House Robber II – LC 213
- #Min Cost Climbing Stairs – LC 746
- #Decode Ways – LC 91
- #Counting Bits – LC 338
- #Divisor Game – LC 1025
- #Frog Jump (basic DP) – GFG
- #Jump Game (DP view) – LC 55
- #Pascal's Triangle – LC 118
After these:
You should define dp[i] clearly without guessing.
️ MEDIUM : 2D DP & Choice-Based States
Write state + transition in English first.
- #Unique Paths – LC 62
- #Unique Paths II – LC 63
- #Minimum Path Sum – LC 64
- #Coin Change – LC 322
- #Coin Change II – LC 518
- #Partition Equal Subset Sum – LC 416
- #Longest Increasing Subsequence – LC 300
- #Longest Common Subsequence – LC 1143
- #Edit Distance – LC 72
- #Longest Palindromic Subsequence – LC 516
Interviewers check:
Can you explain state + transition
HARD : DP Mastery Problems
These test pattern recognition inside DP.
- #Target Sum – LC 494
- #Word Break – LC 139
- #0/1 Knapsack – GFG
- #Unbounded Knapsack – GFG
- #Matrix Chain Multiplication – GFG
- #Regular Expression Matching – LC 10
- #Wildcard Matching – LC 44
- #Distinct Subsequences – LC 115
- #Maximum Alternating Subsequence Sum – LC 1911
- #Interleaving String – LC 97
These require:
- Clean state modeling
- Space optimization awareness
- Zero memorization
DP SOLVING CHECKLIST (INTERVIEW GOLD)
Before coding, always say:
- #What is my state?
- #What are my choices?
- #Base case?
- #Transition?
- #Final answer location?
If you answer these → you win.
Common Interview Killers
- Writing DP without explaining recursion
- Wrong state definition
- Mixing greedy logic
- Memorizing solutions
INTERVIEW REVISION CARD — Pattern 13
1️⃣ Pattern in One Line
"Avoid solving the same subproblem twice — disciplined recursion with memory."
2️⃣ Recognize It When...
- Overlapping subproblems in recursion tree
- Asked for maximum/minimum/count/ways
- Greedy fails — local choice isn't always globally optimal
- Trigger words: "number of ways", "minimum cost", "maximum profit", "can you achieve"
3️⃣ Don't Confuse With...
- Greedy (P9) → greedy commits once; DP explores all choices
- Backtracking (P10) → backtracking generates all; DP counts/optimizes
- Divide & Conquer → D&C subproblems don't overlap; DP subproblems do
4️⃣ Approach in 3 Steps
- #Define state: dp[i] means "best answer for subproblem i"
- #Write transition: dp[i] = f(dp[i-1], dp[i-2], ...)
- #Follow strict order: Recursion → Memoization → Tabulation → Space Optimization
5️⃣ Invariant to Maintain
"dp[i] always contains the correct optimal answer for the subproblem of size i, regardless of how it was computed."
6️⃣ Complexity to Justify
- Time: O(N) or O(N²) — number of unique states × transition cost
- Space: O(N) or O(1) after space optimization
- Why: Each subproblem solved exactly once
7️⃣ Edge Cases to Always Check
- Base cases: dp[0], dp[1] defined correctly
- Empty input — return 0 or base value
- Negative numbers affecting transitions
- Single element array
- K = 0 or target = 0
8️⃣ One Line to Say in Interview
"This has overlapping subproblems, so I'll use DP — define state, write transition, then optimize space if possible."