DSA Sheet - Day 29 Dynamic Programming
⚡ DSA Sheet – Day 29: Dynamic Programming (Core Patterns)
Dynamic Programming is the most important topic for coding interviews. This section covers fundamental patterns like knapsack, subset sum, and coin change.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| 0/1 Knapsack | Solve | Medium | Amazon, Flipkart | |
| Best Time to Buy & Sell Stock I | Solve | Easy | Amazon, Paytm | |
| Target Sum / Subset Sum | Solve | Medium | Amazon, Meta | |
| Coin Change | Solve | Medium | Microsoft, Amazon | |
| Unbounded Knapsack | Solve | Medium | Amazon |
🧠 Key Approaches
- 0/1 Knapsack: Pick / Not Pick (index + capacity)
- Stock I: Track minimum price dynamically
- Subset Sum: Boolean DP (possible / not possible)
- Coin Change: Min coins required (unbounded choice)
- Unbounded Knapsack: Infinite picks allowed
⚡ Quick Cheatsheet
0/1 Knapsack Transition
if(wt[i] <= W)
dp[i][W] = max(
val[i] + dp[i-1][W - wt[i]],
dp[i-1][W]
);
Coin Change (Min Coins)
dp[i] = min(dp[i], 1 + dp[i - coin]);
Stock Buy & Sell
minPrice = min(minPrice, price);
profit = max(profit, price - minPrice);
Subset Sum
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i]];
🔥 Pro Tip
Recognize DP patterns instantly:
- Choice (pick/not pick)? → Knapsack pattern
- Ways / combinations? → Coin change / subset DP
- Min / max optimization? → DP with transitions