Dynamic Programming
Solves complex problems by breaking them down into smaller, overlapping subproblems and storing their results.
The Approach
- Identify the overlapping subproblems and the optimal substructure.
- Define a recurrence relation: how to solve a problem using the results of its subproblems.
- Store the results of subproblems to avoid re-computation (memoization or tabulation).
- Build up the solution from the base cases to the final answer.
Types of Dynamic Programming
Memoization (Top-Down)
Solve recursively and store results in a map or array to avoid re-computing.
DP Table (Calculating Fibonacci)
?
dp[0]?
dp[1]?
dp[2]?
dp[3]?
dp[4]?
dp[5]?
dp[6]Start by filling base cases.
Recurrence Relation
Tabulation (Bottom-Up)
Solve iteratively, filling a DP table from the base cases up to the final solution.
DP Table (Calculating Fibonacci)
?
dp[0]?
dp[1]?
dp[2]?
dp[3]?
dp[4]?
dp[5]?
dp[6]Start by filling base cases.
Recurrence Relation
Common Problems
Climbing Stairs
Dynamic Programming
House Robber
Dynamic Programming
Coin Change
Dynamic Programming
Longest Increasing Subsequence
Dynamic Programming
Longest Common Subsequence
Dynamic Programming