Dynamic Programming

Dynamic Programming (DP) breaks down complex problems into smaller subproblems, storing their results to avoid redundant calculations.

---

Common Patterns and Techniques

1. State Machine / Kadane’s Variants: Tracking maximum/minimum ending states at each index (e.g. Maximum Subarray, Maximum Product Subarray, Maximum Subarray Sum with One Deletion).
2. 0/1 Knapsack & Unbounded Knapsack: Selecting items under capacity constraints.
3. Longest Common Subsequence (LCS) / Edit Distance: Sequence comparison and edit distance alignment.
4. 1D / 2D Grid DP: Path counting or cost optimization on grids.

---

Solved Problems

• 0152 - Maximum Product Subarray
• 1186 - Maximum Subarray Sum with One Deletion