11. Dynamic Programming

🧠 DP Strategy

1. Define State: dp[i] or dp[i][j]? What does it represent?
2. Transition: How do I get to dp[i] from dp[i-1]?
3. Base Case: What is the answer for 0 items?

---

🟢 1D DP: Basics & Linear

• Climbing Stairs
• Fibonacci Number
• Max Sum Without Adjacent Elements
• Minimum Number of Squares
• Lets Party
• Ways to Decode
• Ways to Send the Signal
• Dice Throw
• String Count

🟡 2D DP: Grids & Paths

• Unique Paths in a Grid
• Grid Unique Paths II
• Min Sum Path in Matrix
• Dungeon Princess
• Min Sum Path in Triangle
• Maximum Path in Triangle

🟠 Knapsack Pattern

• Zero One Knapsack
• Unbounded Knapsack
• Buying Candies
• Tushars Birthday Party

🔴 Strings (LCS & Editing)

• Longest Common Subsequence
• Longest Palindromic Subsequence
• Edit Distance
• Distinct Subsequences
• Repeating Subsequence
• Interleaving Strings
• Three Strings
• Regular Expression Match
• Regular Expression II

🟣 MCM & Intervals

• Matrix Chain Multiplication
• Max Wine Profit
• Palindrome Partitioning II
• Russian Doll Envelopes

---