DSA Sheet - Day 30 Dynamic Programming
⚡ DSA Sheet – Day 30: Advanced Dynamic Programming
This is the final step of your DSA journey. These problems combine multiple DP patterns and are frequently asked in top product-based companies.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Longest Common Substring | Solve | Medium | Amazon, Microsoft | |
| Longest Common Subsequence | Solve | Medium | Meta, Oracle | |
| Longest Increasing Subsequence | Solve | Medium | Goldman Sachs, IBM | |
| Edit Distance | Solve | Medium | Adobe, Citrix | |
| Longest Palindromic Subsequence | Solve | Medium | Google, Cisco | |
| Buy & Sell Stocks II | Solve | Medium | Amazon |
🧠 Key Approaches
- LCS / Substring: 2D DP on strings
- LIS: DP OR Binary Search (O(n log n))
- Edit Distance: Insert / Delete / Replace transitions
- Palindrome Subsequence: LCS with reversed string
- Stock II: Greedy OR DP for multiple transactions
⚡ Quick Cheatsheet
Longest Common Subsequence (LCS)
if(s1[i] == s2[j])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
Longest Increasing Subsequence (LIS)
// DP: O(n^2)
// Optimized: Binary Search (Patience Sorting)
Edit Distance
if(s1[i] == s2[j])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min(insert, delete, replace);
Stock Buy & Sell II
profit += max(0, prices[i] - prices[i-1]);
🔥 Pro Tip
Final DP recognition patterns:
- Two strings? → LCS / Edit Distance
- Increasing sequence? → LIS
- Palindrome? → Reverse + LCS
- Multiple transactions? → Stock DP / Greedy