Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting two key attributes: optimal substructure and overlapping subproblems.

Key Concepts

1. Optimal Substructure: The optimal solution to the problem contains optimal solutions to its subproblems.
2. Overlapping Subproblems: The same subproblems are encountered multiple times during problem-solving.

Approaches to DP

1. Top-Down (Memoization): Solve the problem recursively, but store the results of subproblems to avoid redundant calculations.
2. Bottom-Up (Tabulation): Build up solutions to subproblems iteratively, starting from the simplest cases.

Common Patterns

1. 1D DP: Problems involving a single state dimension

   • Examples: Fibonacci, Climbing Stairs, House Robber

2. 2D DP: Problems involving two state dimensions

   • Examples: Longest Common Subsequence, Edit Distance, Minimum Path Sum

3. Knapsack Problems: Optimization problems with constraints

   • Examples: 0/1 Knapsack, Unbounded Knapsack

4. String DP: Problems involving string manipulations

   • Examples: Longest Palindromic Substring, Regular Expression Matching

5. Interval DP: Problems involving intervals

   • Examples: Matrix Chain Multiplication, Burst Balloons

Common Problems

1. Fibonacci Numbers
2. Longest Increasing Subsequence
3. Coin Change
4. Longest Common Subsequence
5. Knapsack Problem