DSA Sheet - Day 32 Dynamic Programming
⚡ DSA Sheet – Day 32: Advanced Dynamic Programming
This section focuses on hard DP problems that test deep understanding of state transitions, optimization, and pattern recognition. These are commonly asked in top-tier interviews.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Minimum Partition | Solve | Hard | Amazon, Meta | |
| Maximum Product Subarray | Solve | Medium | Amazon, LinkedIn | |
| Wildcard Pattern Matching | Solve | Hard | Microsoft, Amazon | |
| Longest Bitonic Subsequence | Solve | Hard | Google, Meta | |
| Egg Dropping Problem | Solve | Hard | Amazon, Microsoft |
🧠 Key Approaches
- Minimum Partition: Convert to subset sum → minimize difference
- Max Product Subarray: Track both max & min (handle negatives)
- Wildcard Matching: DP with '*' (multiple) and '?' (single)
- Bitonic Subsequence: LIS (forward) + LDS (reverse)
- Egg Dropping: Try all floors → minimize worst case
⚡ Quick Cheatsheet
Maximum Product Subarray
int maxP = nums[0], minP = nums[0], ans = nums[0];
for(int i = 1; i < n; i++){
if(nums[i] < 0) swap(maxP, minP);
maxP = max(nums[i], maxP * nums[i]);
minP = min(nums[i], minP * nums[i]);
ans = max(ans, maxP);
}
Wildcard Matching
if(p[j] == '*')
dp[i][j] = dp[i][j-1] || dp[i-1][j];
Longest Bitonic Subsequence
ans = max(LIS[i] + LDS[i] - 1);
Egg Dropping Problem
for(int k = 1; k <= f; k++){
res = 1 + max(dp[e-1][k-1], dp[e][f-k]);
}
🔥 Pro Tip
These are pattern-heavy DP problems. Focus on:
- State definition clarity
- Transition correctness
- Optimizing brute force recursion