Chapter 6: Dynamic Programming
Master dynamic programming techniques including 1D/2D DP, memoization, and classic patterns. Learn when and where to use DP.
1. Dynamic Programming Fundamentals
📌 When and Where to Use
- Overlapping subproblems: Same subproblems computed multiple times
- Optimal substructure: Optimal solution contains optimal solutions to subproblems
- Optimization problems: Finding maximum, minimum, or count
- Real-world example: Stock trading (max profit), text alignment, resource allocation, or shortest path problems
DP Approach
- Identify subproblems: What are the smaller versions of the problem?
- Define state: What information do we need to track?
- Find recurrence: How do we build solution from subproblems?
- Base cases: What are the smallest subproblems?
- Build solution: Fill DP table bottom-up or use memoization
2. Fibonacci (Classic DP Example)
Example: Fibonacci with Memoization
def fibonacci(n, memo={}):
"""
Calculate nth Fibonacci number using memoization.
Args:
n: Position in Fibonacci sequence
memo: Dictionary to cache computed values
Returns:
nth Fibonacci number
"""
# Step 1: Base cases
if n <= 1:
return n
# Step 2: Check if already computed
if n in memo:
return memo[n]
# Step 3: Compute and store in memo
# Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
# Step 4: Return cached result
return memo[n]Step-by-Step Code Walkthrough:
Step 1 - Base Cases: fib(0) = 0, fib(1) = 1.
Step 2 - Check Memo: If already computed, return cached value (avoids recomputation).
Step 3 - Compute: Calculate using recurrence relation and store in memo.
Step 4 - Return: Return the computed value.
Time Complexity: O(n) - each number computed once
Space Complexity: O(n) - memo dictionary
Bottom-Up Approach
def fibonacci_bottom_up(n):
"""
Calculate nth Fibonacci using bottom-up DP.
Args:
n: Position in Fibonacci sequence
Returns:
nth Fibonacci number
"""
# Step 1: Base cases
if n <= 1:
return n
# Step 2: Initialize DP array
# dp[i] represents ith Fibonacci number
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Step 3: Fill DP array bottom-up
for i in range(2, n + 1):
# Step 3a: Build solution from previous subproblems
dp[i] = dp[i - 1] + dp[i - 2]
# Step 4: Return result
return dp[n]3. Climbing Stairs
Example: Ways to Climb Stairs
Problem: You can climb 1 or 2 steps at a time. How many ways to reach the top?
def climb_stairs(n):
"""
Count ways to climb n stairs (1 or 2 steps at a time).
Args:
n: Number of stairs
Returns:
Number of distinct ways to climb
"""
# Step 1: Base cases
if n <= 2:
return n
# Step 2: Initialize DP array
# dp[i] = ways to reach step i
dp = [0] * (n + 1)
dp[1] = 1 # One way: 1 step
dp[2] = 2 # Two ways: 1+1 or 2
# Step 3: Fill DP array
for i in range(3, n + 1):
# Step 3a: Recurrence relation
# To reach step i, we can come from step i-1 or i-2
# Ways to reach i = ways to reach (i-1) + ways to reach (i-2)
dp[i] = dp[i - 1] + dp[i - 2]
# Step 4: Return result
return dp[n]Step-by-Step Code Walkthrough:
Step 1 - Base Cases: 1 stair = 1 way, 2 stairs = 2 ways.
Step 2 - Initialize: DP array stores ways to reach each step.
Step 3 - Fill DP: For each step i:
- Step 3a: Ways to reach i = ways to reach (i-1) + ways to reach (i-2)
- We can come from previous step (1 step) or step before that (2 steps)
Step 4 - Return: Return ways to reach top step.
Note: This is essentially Fibonacci! dp[i] = fib(i+1)
4. House Robber
Example: Maximum Money Without Adjacent
Problem: Rob houses to maximize money, but can't rob two adjacent houses.
def rob(nums):
"""
Maximum money from robbing houses (no adjacent).
Args:
nums: List of money in each house
Returns:
Maximum money that can be robbed
"""
# Step 1: Handle edge cases
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# Step 2: Initialize DP array
# dp[i] = maximum money from robbing houses 0 to i
n = len(nums)
dp = [0] * n
dp[0] = nums[0] # Only one house
dp[1] = max(nums[0], nums[1]) # Two houses: take max
# Step 3: Fill DP array
for i in range(2, n):
# Step 3a: Decision at house i
# Option 1: Rob house i + best from houses 0 to i-2
# Option 2: Skip house i, take best from houses 0 to i-1
dp[i] = max(
nums[i] + dp[i - 2], # Rob current house
dp[i - 1] # Skip current house
)
# Step 4: Return maximum
return dp[n - 1]Step-by-Step Code Walkthrough:
Step 1 - Edge Cases: Handle empty array and single house.
Step 2 - Initialize:
- dp[0] = money from first house
- dp[1] = max of first two houses
Step 3 - Fill DP: For each house i:
- Step 3a: Two choices:
- Rob house i: nums[i] + dp[i-2] (can't rob i-1)
- Skip house i: dp[i-1] (best from previous houses)
- Take the maximum
Step 4 - Return: Maximum money from all houses.
5. Longest Common Subsequence (2D DP)
📌 When and Where to Use
- String comparison: Finding common subsequences
- Edit distance: Similarity between strings
- Real-world example: DNA sequence alignment, diff algorithms, or version control systems
Example: LCS
def longest_common_subsequence(text1, text2):
"""
Find length of longest common subsequence.
Args:
text1: First string
text2: Second string
Returns:
Length of LCS
"""
m, n = len(text1), len(text2)
# Step 1: Initialize 2D DP array
# dp[i][j] = LCS of text1[0:i] and text2[0:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Step 2: Fill DP array
for i in range(1, m + 1):
for j in range(1, n + 1):
# Step 2a: If characters match
if text1[i - 1] == text2[j - 1]:
# Extend LCS from previous subproblem
dp[i][j] = dp[i - 1][j - 1] + 1
else:
# Step 2b: Characters don't match
# Take maximum of two options:
# Option 1: Skip character from text1
# Option 2: Skip character from text2
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Step 3: Return result
return dp[m][n]Step-by-Step Code Walkthrough:
Step 1 - Initialize: 2D DP array, dp[i][j] = LCS of first i chars of text1 and first j chars of text2.
Step 2 - Fill DP: For each position (i, j):
- Step 2a: If characters match, extend LCS: dp[i][j] = dp[i-1][j-1] + 1
- Step 2b: If don't match, take max of skipping one character from either string
Step 3 - Return: dp[m][n] contains LCS of entire strings.
Example:
text1 = "abcde", text2 = "ace"
LCS = "ace" (length 3)
6. Coin Change
Example: Minimum Coins for Amount
Problem: Find minimum number of coins to make amount.
def coin_change(coins, amount):
"""
Find minimum coins to make amount.
Args:
coins: List of coin denominations
amount: Target amount
Returns:
Minimum number of coins, or -1 if impossible
"""
# Step 1: Initialize DP array
# dp[i] = minimum coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins for amount 0
# Step 2: Fill DP array
for i in range(1, amount + 1):
# Step 2a: Try each coin
for coin in coins:
# Step 2b: Check if coin can be used
if coin <= i:
# Step 2c: Update minimum
# Use this coin + minimum for remaining amount
dp[i] = min(dp[i], dp[i - coin] + 1)
# Step 3: Return result
# If dp[amount] is still infinity, impossible
return dp[amount] if dp[amount] != float('inf') else -1Step-by-Step Code Walkthrough:
Step 1 - Initialize: DP array with infinity (impossible), dp[0] = 0 (base case).
Step 2 - Fill DP: For each amount i:
- Step 2a: Try each coin denomination
- Step 2b: If coin <= amount, can use it
- Step 2c: Update minimum: dp[i] = min(dp[i], dp[i-coin] + 1)
Step 3 - Return: If dp[amount] is infinity, impossible; otherwise return minimum coins.
📚 Chapter Summary
- 1D DP: Problems with one changing parameter (stairs, house robber)
- 2D DP: Problems with two changing parameters (LCS, edit distance)
- Memoization: Top-down approach (recursive with caching)
- Bottom-up: Iterative approach (fill DP table)
- Key Steps: Identify subproblems → Define state → Find recurrence → Base cases → Build solution
Key Takeaway: DP is about breaking problems into overlapping subproblems and storing results to avoid recomputation. Look for optimization problems with optimal substructure.