DSA Sheet - Day 31 Dynamic Programming
⚡ DSA Sheet – Day 31: Advanced Dynamic Programming (Part 3)
This section focuses on partition DP and combinatorics-based problems. These are among the most important patterns for high-level interviews.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Nth Catalan Number | Solve | Medium | Google, Amazon | |
| Unique BSTs | Solve | Medium | Google, Amazon | |
| Rod Cutting | Solve | Hard | Adobe, Apple | |
| Palindromic Partitioning (Min Cuts) | Solve | Medium | Meta, Amazon | |
| Matrix Chain Multiplication (MCM) | Solve | Hard | Amazon, Google |
🧠 Key Approaches
- Catalan / Unique BST: Count structures → partition into left & right
- Rod Cutting: Unbounded knapsack pattern
- Palindrome Partitioning: DP on substrings + palindrome precompute
- MCM: Partition DP → try all splits (k)
⚡ Quick Cheatsheet
Catalan / Unique BST
for(int n = 0; n <= N; n++){
for(int i = 0; i < n; i++){
dp[n] += dp[i] * dp[n - 1 - i];
}
}
Rod Cutting (Unbounded Knapsack)
dp[i] = max(dp[i], price[j] + dp[i - j]);
Palindrome Partitioning (Min Cuts)
if(isPal[i][j])
dp[i] = min(dp[i], 1 + dp[j + 1]);
Matrix Chain Multiplication (MCM)
for(int k = i; k < j; k++){
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k+1][j] + cost);
}
🔥 Pro Tip
Recognize partition DP when:
- You split a problem into two parts
- You try all possible partition points (k)
- You minimize or maximize a result