Dynamic Programming: From Zero to Hero
- ๐ฏ What is Dynamic Programming?
- ๐ The Core Idea
- ๐ Two Approaches to DP (Top-Down vs Bottom-Up)
- ๐ Two Key Properties of DP
- ๐งฉ Example 1: Fibonacci Numbers
- ๐๏ธ DP Framework: 5-Step Process
- ๐งฉ Example 2: Climbing Stairs
- ๐ฆ DP Categories & Patterns
- ๐งฉ Example 3: Unique Paths (2D DP)
- ๐ฐ Example 4: Coin Change (Classic DP)
- 1D vs 2D DP (Very Important)
- ๐ How to Identify DP Problems
- ๐ ๏ธ DP Implementation Patterns
- ๐จ Common Mistakes & How to Avoid Them
- ๐ Memoization vs Tabulation
- ๐ DP Problem-Solving Checklist
- ๐ Space Optimization Techniques
- ๐ฏ Practice Problems by Difficulty
- ๐ง Mental Models for DP
- ๐ Resources for Practice
- ๐ช Final Summary
๐ฏ What is Dynamic Programming?โ
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their solutions.
Three key concepts:
- A problem can be broken into smaller subproblems
- Those subproblems repeat
- We can store their answers and reuse them
๐ Oneโsentence definition:
Dynamic Programming = Recursion + Memory
๐ก Simple Analogy: Imagine climbing stairs. To reach step 10, you need to know how to reach step 9. To reach step 9, you need step 8... DP remembers solutions to these smaller steps!
๐ The Core Ideaโ
Solving big problem
โ
Break into smaller problems
โ
Solve & remember solutions
โ
Reuse solutions to solve bigger problem
Key Properties of DP Problems:โ
-
Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems
- The "Optimal" solution to the big problem can be constructed from the "Optimal" solutions of its subproblems.
- If you want the shortest path from A to C, and it goes through B, the path must include the shortest path from A to B.
-
Overlapping Subproblems: Same subproblems are solved multiple times
- This means the problem can be broken down into smaller versions of itself, and those smaller versions repeat.
๐ Two Approaches to DP (Top-Down vs Bottom-Up)โ
There are two ways to implement DP. Think of them as "The Lazy Way" and "The Organized Way."
Method 1: Top-Down (Memoization)โ
You start with the big problem and break it down. If you've solved a subproblem before, you look up the answer in your "notebook" (usually a dictionary or array).
- Vibe: "I'll solve it when I need it, and save the answer for later."
- Tool: Recursion + Cache.
flowchart LR
Call --> CheckCache
CheckCache -->|Found| Return
CheckCache -->|Not Found| Compute
Compute --> Save
Save --> Return
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
Method 2: Bottom-Up (Tabulation)โ
You start with the smallest possible subproblems (base cases) and fill out a table until you reach the goal.
- Vibe: "Let's build a foundation from the ground up."
- Tool: Iteration (Loops) + Table (Array/Grid).
flowchart LR
Base --> DP1 --> DP2 --> DP3 --> Answer
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
โ Pros: No recursion, often faster
๐ Two Key Properties of DP (Must Memorize)โ
1. Overlapping Subproblemsโ
Same subproblem appears again and again
graph TD
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> C
2. Optimal Substructureโ
The optimal solution of a problem depends on optimal solutions of subproblems
Examples:
- Shortest path
- Maximum profit
- Minimum steps
๐งฉ Example 1: Fibonacci Numbersโ
Problem: Find the nth Fibonacci numberโ
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n > 1
Call Tree Explosionโ
flowchart TD
F5 --> F4
F5 --> F3
F4 --> F3
F4 --> F2
F3 --> F2
F3 --> F1
โ Problem: fib(3) and fib(2) are computed multiple times
1. Brute Force (Recursive) - โ Inefficientโ
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Time: O(2โฟ) - Exponential!
2. Memoization (Top-Down DP) - โ Efficientโ
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# Time: O(n), Space: O(n)
3. Tabulation (Bottom-Up DP) - โ Most Efficientโ
def fib_tab(n):
if n <= 1:
return n
# 1. State: dp[i] is the i-th Fibonacci number
dp = [0] * (n + 1)
# 2. Base Cases
dp[0] = 0
dp[1] = 1
# 4. Order: 2 to n
for i in range(2, n + 1):
# 3. Recurrence Relation
dp[i] = dp[i-1] + dp[i-2]
# 5. Final Answer
return dp[n]
# Time: O(n), Space: O(n)
Visualization:
Index: 0 1 2 3 4 5
dp = [0, 1, 0, 0, 0, 0] # Initial
i=2: dp[2] = 1 + 0 = 1
dp = [0, 1, 1, 0, 0, 0]
i=3: dp[3] = 1 + 1 = 2
dp = [0, 1, 1, 2, 0, 0]
i=4: dp[4] = 2 + 1 = 3
dp = [0, 1, 1, 2, 3, 0]
i=5: dp[5] = 3 + 2 = 5
dp = [0, 1, 1, 2, 3, 5]
4. Space Optimized - โ O(1) Spaceโ
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1 # F(0), F(1)
for i in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
# Time: O(n), Space: O(1)
๐๏ธ DP Framework: 5-Step Processโ
Step 1: Define the Stateโ
What does dp[i] represent?
Example:
dp[i]= i-th Fibonacci number
Step 2: Define the Base Casesโ
What are the smallest problems with known solutions?
Example:
dp[0] = 0,dp[1] = 1
Step 3: Define the Recurrence Relation (What are the choices?)โ
How does dp[i] depend on smaller states?
Example:
dp[i] = dp[i-1] + dp[i-2]
Step 4: Determine Order of Computation (What is the transition?)โ
Should we go bottom-up or top-down?
Example: Compute from
dp[0]todp[n]
Step 5: Return the Answerโ
Which state contains the final answer?
Example: Return
dp[n]
๐งฉ Example 2: Climbing Stairsโ
Problem: You can climb 1 or 2 steps at a time. How many ways to reach the top?โ
Observation: This is Fibonacci! ways(n) = ways(n-1) + ways(n-2)
n = 1: [1] โ 1 way
n = 2: [1,1], [2] โ 2 ways
n = 3: [1,1,1], [1,2], [2,1] โ 3 ways
n = 4: โ 5 ways
DP Solution:โ
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1 # 1 way to reach step 1
dp[2] = 2 # 2 ways to reach step 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Space optimized:
def climbStairs_opt(n):
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
State & Transition:โ
- State:
dp[i]= number of ways to reach stepi - Transition:
dp[i] = dp[i-1] + dp[i-2]
graph LR
S0 --> S1
S0 --> S2
S1 --> S2
S1 --> S3
Visual Explanation:
To reach step i:
1. Come from step i-1 (take 1 step)
2. Come from step i-2 (take 2 steps)
Total ways(i) = ways(i-1) + ways(i-2)
๐ฆ DP Categories & Patternsโ
1. 1D DP (Linear Problems)โ
โโโโโฌโโโโฌโโโโฌโโโโฌโโโโ
โdp0โdp1โdp2โdp3โdp4โ
โโโโโดโโโโดโโโโดโโโโดโโโโ
โ depends on previous 1-2 elements
Examples: Fibonacci, Climbing Stairs, House Robber
2. 2D DP (Grid/Matrix Problems)โ
Problem: You are at the top-left of a grid. You can only move Right or Down. How many ways can you reach the bottom-right?
To get to any cell, you must have come from either the Top or the Left. Each cell in the table above stores the number of ways to reach that specific spot. We fill it row by row, adding the values from the neighbors we already calculated.
0 1 2 3
0 โโโโโฌโโโโฌโโโโฌโโโโ
โ S โ โ โ โ โ โ โ
1 โโโโโผโโโโผโโโโผโโโโค
โ โ โ โ โ โ โ โ โ
2 โโโโโผโโโโผโโโโผโโโโค
โ โ โ โ โ โ โ E โ
3 โโโโโดโโโโดโโโโดโโโโ
Examples: Unique Paths, Minimum Path Sum
3. Knapsack DP (Selection Problems)โ
Choose items with constraints (weight, value)
4. Interval DPโ
Problems involving intervals/ranges
5. Tree DPโ
DP on tree structures
๐งฉ Example 3: Unique Paths (2D DP)โ
Problem: Robot at top-left, can only move right or down. How many unique paths to bottom-right?โ
Grid: 3ร3
S โ โ
โ โ
โ โ E
Answer: 6 paths
DP Solution:โ
def uniquePaths(m, n):
# dp[i][j] = ways to reach cell (i,j)
dp = [[0] * n for _ in range(m)]
# Base cases
for i in range(m):
dp[i][0] = 1 # First column
for j in range(n):
dp[0][j] = 1 # First row
# Fill DP table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
Visualization (3ร3 grid):
Initial:
1 1 1
1 0 0
1 0 0
After filling:
1 1 1
1 2 3
1 3 6 โ Answer: 6
Explanation:
- Can only come from above or left
dp[i][j] = dp[i-1][j] + dp[i][j-1]
๐ฐ Example 4: Coin Change (Classic DP)โ
Problem: Minimum coins to make amountโ
Coins: [1, 2, 5]
Amount: 11
Answer: 3 (5 + 5 + 1)
State:โ
dp[x] = minimum coins needed to make amount x
Transition:โ
dp[x] = min(dp[x - coin] + 1)
flowchart TD
A[Amount x]
A -->|Try coin 1| B[x-1]
A -->|Try coin 2| C[x-2]
A -->|Try coin 5| D[x-5]
DP Solution:โ
def coinChange(coins, amount):
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins needed for amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Step-by-step (coins=[1,2,5], amount=11):
dp[0] = 0
dp[1] = min(dp[0]+1) = 1
dp[2] = min(dp[1]+1, dp[0]+1) = min(2,1) = 1
dp[3] = min(dp[2]+1, dp[1]+1) = min(2,2) = 2
...
dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(2+1, 3+1, 2+1) = 3
1D vs 2D DP (Very Important)โ
1D DPโ
graph LR
dp0 --> dp1 --> dp2 --> dp3
Examples: Fibonacci, Climbing stairs, Coin change
2D DPโ
graph TD
dp00 --> dp01 --> dp02
dp10 --> dp11 --> dp12
dp20 --> dp21 --> dp22
Examples: Knapsack, Longest Common Subsequence, Edit Distance
Classic 2D DP: Longest Common Subsequence (LCS)โ
State:โ
dp[i][j] = LCS length of text1[:i] and text2[:j]
Transition:โ
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
flowchart TD
A[dp[i-1][j]] --> C[dp[i][j]]
B[dp[i][j-1]] --> C
D[dp[i-1][j-1]] --> C
Space Optimization (Advanced but Powerful)โ
Many DP problems only depend on previous row
flowchart LR
Row1 --> Row2 --> Row3
So you can reduce:
O(nยฒ)โO(n)
DP Problem Pattern Mapโ
mindmap
root((Dynamic Programming))
1D DP
Fibonacci
Stairs
Coin Change
2D DP
Knapsack
LCS
Edit Distance
State Compression
Bitmask DP
Interval DP
Burst Balloons
๐ How to Identify DP Problemsโ
Ask These Questions:โ
- Can it be broken into subproblems?
- Do subproblems overlap? (Would recursion repeat calculations?)
- Is there optimal substructure? (Can we build optimal solution from optimal subproblems?)
Common DP Problem Patterns:โ
1. "Count the number of ways..." โ Often DP
2. "Find minimum/maximum..." โ Often DP
3. "Find if possible..." โ Often DP
4. Grid/matrix problems โ Often 2D DP
5. String problems โ Often 2D DP
How to Recognize a DP Problem (Interview Gold โญ)โ
Look for these keywords:
- "maximum / minimum"
- "number of ways"
- "longest / shortest"
- "can you reach"
- "optimal"
๐ ๏ธ DP Implementation Patternsโ
Pattern 1: Fibonacci Styleโ
# dp[i] depends on dp[i-1], dp[i-2]
dp = [0] * (n+1)
dp[0], dp[1] = base_cases
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
Pattern 2: Grid DPโ
# dp[i][j] depends on dp[i-1][j], dp[i][j-1]
dp = [[0]*cols for _ in range(rows)]
# Initialize first row/col
for i in range(rows):
for j in range(cols):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Pattern 3: Knapsack Styleโ
# dp[i][w] = max value with first i items and weight w
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, W+1):
if weight[i-1] <= w:
dp[i][w] = max(dp[i-1][w],
dp[i-1][w-weight[i-1]] + value[i-1])
else:
dp[i][w] = dp[i-1][w]
Pattern 4: LCS (Longest Common Subsequence)โ
# dp[i][j] = LCS of first i chars of A and j chars of B
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
๐จ Common Mistakes & How to Avoid Themโ
Mistake 1: Not defining state clearlyโ
Fix: Write down what dp[i] means before coding
Mistake 2: Wrong base casesโ
Fix: Test with smallest inputs (n=0, n=1)
Mistake 3: Off-by-one errorsโ
Fix: Use 0-indexed or 1-indexed consistently
Mistake 4: Forgetting to initializeโ
Fix: Always initialize DP array with appropriate values
Mistake 5: Wrong recurrence relationโ
Fix: Draw small examples to verify logic
๐ Memoization vs Tabulationโ
Memoization (Top-Down)โ
def solve(n, memo={}):
if n in memo: return memo[n]
if base_case: return value
memo[n] = solve(n-1) + solve(n-2)
return memo[n]
Pros:
- More intuitive (like recursion)
- Only computes needed states
Cons:
- Recursion depth limit
- Function call overhead
Tabulation (Bottom-Up)โ
dp = [0]*(n+1)
for i in range(1, n+1):
dp[i] = dp[i-1] + dp[i-2]
Pros:
- No recursion limit
- Often faster
- Easier to optimize space
Cons:
- Might compute unnecessary states
- Less intuitive initially
๐ DP Problem-Solving Checklistโ
Before Coding:โ
- Identify this is a DP problem
- Define state variables clearly
- Write recurrence relation on paper
- Determine base cases
- Decide memoization vs tabulation
While Coding:โ
- Initialize DP table properly
- Handle edge cases
- Verify recurrence with small example
- Check indices/off-by-one errors
After Coding:โ
- Test with given examples
- Test with edge cases (empty, minimum size)
- Consider space optimization
- Analyze time/space complexity
๐ Space Optimization Techniquesโ
1. Rolling Array (for dependencies on few previous states)โ
# Before: dp[i] depends on dp[i-1], dp[i-2]
# After: Keep only last 2 values
prev2, prev1 = 0, 1
for i in range(2, n+1):
current = prev1 + prev2
prev2, prev1 = prev1, current
2. Reuse Input Array (if allowed)โ
# Modify input array in place as DP table
3. Alternate Rows in 2D DPโ
# When dp[i][j] only depends on previous row
dp_prev = [0]*n
dp_curr = [0]*n
for i in range(1, m):
for j in range(1, n):
dp_curr[j] = dp_prev[j] + dp_curr[j-1]
dp_prev, dp_curr = dp_curr, dp_prev
๐ DP Templateโ
def dp_solution(inputs):
# Step 1: Identify state variables
# dp[i] or dp[i][j] or dp[i][j][k]...
# Step 2: Create DP table
n = len(inputs)
dp = [0] * (n + 1) # or 2D array
# Step 3: Base cases
dp[0] = base_value
# or initialize first row/col
# Step 4: State transition
for i in range(1, n + 1):
for option in options:
dp[i] = max/min(dp[i], dp[prev_state] + something)
# or dp[i] = dp[i-1] + dp[i-2] etc.
# Step 5: Return answer
return dp[n] # or dp[-1][-1] for 2D
๐ฏ Practice Problems by Difficultyโ
Beginner Level:โ
- Fibonacci Number (LeetCode 509)
- Climbing Stairs (LeetCode 70)
- Best Time to Buy/Sell Stock (LeetCode 121)
- Maximum Subarray (LeetCode 53)
Intermediate Level:โ
- House Robber (LeetCode 198)
- Coin Change (LeetCode 322)
- Longest Increasing Subsequence (LeetCode 300)
- Unique Paths (LeetCode 62)
Advanced Level:โ
- Edit Distance (LeetCode 72)
- Longest Common Subsequence (LeetCode 1143)
- Word Break (LeetCode 139)
- Knapsack Problems
๐ง Mental Models for DPโ
Model 1: The "Building Up" Modelโ
Think: "If I know solutions for all smaller problems, how do I solve the current one?"
Model 2: The "Decision Tree" Modelโ
At each step, you make a choice. DP finds the optimal path through the tree.
Model 3: The "Caching" Modelโ
Remember expensive computations so you don't repeat them.
Model 4: The "State Machine" Modelโ
Your state represents where you are in the problem. Transitions represent decisions.
๐ Resources for Practiceโ
Interactive Platforms:โ
- LeetCode: Filter by "Dynamic Programming" tag
- AtCoder DP Contest: 26 classic DP problems
- CSES Problem Set: Excellent DP section
Recommended Learning Order:โ
- Fibonacci & climbing stairs
- Grid problems (unique paths)
- Knapsack problems
- String DP (LCS, edit distance)
- Advanced DP (tree DP, bitmask DP)
๐ช Final Summary: DP Mastery Pathโ
Level 1: Foundationโ
- Understand recursion with overlapping subproblems
- Learn memoization pattern
- Practice Fibonacci, climbing stairs
Level 2: Core Patternsโ
- Master 1D DP patterns
- Learn to define states and transitions
- Practice house robber, coin change
Level 3: Advanced Patternsโ
- Master 2D DP (grid problems)
- Understand knapsack patterns
- Practice unique paths, LCS
Level 4: Optimizationโ
- Space optimization techniques
- Time complexity analysis
- Real-world DP applications
Level 5: Masteryโ
- Recognize DP patterns quickly
- Derive recurrence relations
- Solve complex DP problems
Golden Rule: If you see overlapping subproblems and optimal substructure, think DP!
Remember: Practice is key. Start with simple problems and gradually increase difficulty. Draw diagrams, write recurrence relations, and don't get discouraged!
You've got this! ๐ Every DP master started where you are now. Keep practicing!