DP = Remembering answers instead of recalculating them. That's it.
✅ Overlapping subproblems?
✅ Need max/min value?
✅ Count number of ways?
✅ Check if something is possible?
YES to 2+ = DP!
Every problem has 3 forms:
| Approach | Speed | Code Style |
|---|---|---|
| Recursion | 💀 O(2^n) | Clean & slow |
| Memoization | ⚡ O(n) or O(n²) | Recursion + cache |
| Tabulation | 🚀 O(n) or O(n²) | Loops, no recursion |
Rule: Start with recursion → Add memoization → Convert to tabulation
Fibonacci (fibonacci.cpp)
Classic DP intro. Shows 2^n → O(n) transformation.
Climbing Stairs (climbingStairs.cpp)
Count ways to reach step n (1 or 2 steps at a time). Spoiler: It's Fibonacci!
0/1 Knapsack (knapsack.cpp)
The most important DP problem ever. Master this, master DP.
Decision: Include item OR Exclude item
dp[i][j] = max(val[i] + dp[i-1][j-wt[i]], dp[i-1][j])
Variants in same file:
- Target Sum
- Unbounded Knapsack
- Rod Cutting
LCS - Longest Common Subsequence (longestComSeq.cpp)
str1: "abcdeg" | If match: dp[i][j] = 1 + dp[i-1][j-1]
str2: "abedg" | If no match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
LCS: "abdg" ✓
LCS - Longest Common Substring (longestComSubstr.cpp)
Like LCS but continuous only. If mismatch → reset to 0!
Bonus: Longest Increasing Subsequence using LCS trick.
Matrix Chain Multiplication (matrixChainMiltiplMCM.cpp)
Try all split points, pick cheapest. O(n³) complexity.
for(int k=i; k<j; k++) {
cost = dp[i][k] + dp[k+1][j] + arr[i-1]*arr[k]*arr[j];
}Bonus: Minimum Partition problem included.
Wildcard Matching (widlcardCatlan.cpp)
Match strings with ? (single char) and * (any sequence).
Catalan Numbers (widlcardCatlan.cpp)
Appears everywhere: BSTs, parentheses, mountain ranges.
C(n) = Σ C(i) * C(n-i-1)
Fibonacci: 2^n → O(n)
Climbing Stairs: 2^n → O(n)
Knapsack: 2^n → O(n×W)
LCS: 2^(n+m) → O(n×m)
MCM: 2^n → O(n³)
Catalan: 4^n → O(n²)
Wrong Answer?
- Check base cases (n=0, n=1)
- Print your DP table
- Array indices off-by-one?
TLE (Time Limit)?
- Still using pure recursion?
- Add memoization!
MLE (Memory Limit)?
- Reduce dimensions (2D→1D)
- Only store what you need
Common Bugs:
- Forgot to initialize dp with -1
- Wrong loop bounds (<=n vs <n)
- Passing dp by value instead of reference
1. Define state: What does dp[i] mean?
2. Find recurrence: How to calculate dp[i]?
3. Base cases: Smallest subproblems?
4. Build solution: Memo or tab?
# Basics
g++ fibonacci.cpp -o fib && ./fib
g++ climbingStairs.cpp -o climb && ./climb
# Knapsack family
g++ knapsack.cpp -o ks && ./ks
# String DP
g++ longestComSeq.cpp -o lcs && ./lcs
# Advanced
g++ matrixChainMiltiplMCM.cpp -o mcm && ./mcmWeek 1: Fib + Climbing Stairs → Understand the 3 approaches
Week 2: Knapsack variants → Master include/exclude pattern
Week 3: LCS problems → String DP techniques
Week 4: MCM + Catalan → Advanced patterns
💡 Draw recursion tree to spot overlaps
💡 Brute force first, optimize later
💡 Test with n=0, n=1, n=2 manually
💡 DP takes practice - be patient!
Add problems with all 3 approaches. Keep code clean. Update README.
DP looks scary but it's just patterns. Master these, you're unstoppable! 🚀
Made with ☕ and persistence