1-Dimensional DP
Introduction to dynamic programming with 1D problems. Learn overlapping subproblems, optimal substructure, and memoization.
Dynamic Programming (DP) is a technique for solving problems with overlapping subproblems and optimal substructure. Instead of recomputing the same subproblems, we store their solutions.
When to Use DP
- Optimal substructure: Optimal solution contains optimal solutions to subproblems
- Overlapping subproblems: Same subproblems are solved multiple times
If a problem has these properties, DP can often improve exponential time to polynomial.
Top-Down (Memoization)
Start from the original problem and recursively solve subproblems, caching results:
use std::collections::HashMap;
fn fib_memo(n: usize, memo: &mut HashMap<usize, usize>) -> usize {
if let Some(&result) = memo.get(&n) {
return result;
}
if n <= 1 {
return n;
}
let result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
memo.insert(n, result);
result
}
Bottom-Up (Tabulation)
Solve subproblems in order, building up to the final solution:
fn fib_tab(n: usize) -> usize {
if n <= 1 {
return n;
}
let mut dp = vec![0; n + 1];
dp[1] = 1;
for i in 2..=n {
dp[i] = dp[i - 1] + dp[i - 2];
}
dp[n]
}
Space Optimization
Often we only need the last few values:
fn fib_optimized(n: usize) -> usize {
if n <= 1 {
return n;
}
let (mut prev2, mut prev1) = (0, 1);
for _ in 2..=n {
let current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
prev1
}
Which Approach?
Top-down is often easier to write (just add memoization to recursion). Bottom-up is usually more efficient (no recursion overhead) and can be space-optimized.
Problem: Climbing Stairs
You can climb 1 or 2 steps at a time. How many ways to reach step n?
def climb_stairs(n):
if n <= 2:
return n
prev2, prev1 = 1, 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# dp[i] = dp[i-1] + dp[i-2]
# Same as Fibonacci!
Problem: House Robber
Rob houses for maximum profit without robbing adjacent houses:
fn rob(nums: &[i32]) -> i32 {
if nums.is_empty() {
return 0;
}
if nums.len() == 1 {
return nums[0];
}
// dp[i] = max money robbing houses 0..i
let mut prev2 = nums[0];
let mut prev1 = nums[0].max(nums[1]);
for i in 2..nums.len() {
let current = prev1.max(prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
prev1
}
nums = [2, 7, 9, 3, 1]
dp[0] = 2 (rob house 0)
dp[1] = max(2, 7) = 7 (rob house 1)
dp[2] = max(7, 2+9) = 11 (rob houses 0, 2)
dp[3] = max(11, 7+3) = 11
dp[4] = max(11, 11+1) = 12
Answer: 12 (rob houses 0, 2, 4)
Problem: Min Cost Climbing Stairs
Each step has a cost. Find minimum cost to reach the top:
def min_cost_climbing_stairs(cost):
n = len(cost)
if n <= 1:
return 0
prev2, prev1 = cost[0], cost[1]
for i in range(2, n):
current = cost[i] + min(prev1, prev2)
prev2 = prev1
prev1 = current
return min(prev1, prev2)
Problem: Maximum Subarray (Kadane's Algorithm)
Find the contiguous subarray with the largest sum:
def max_subarray(nums):
max_sum = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
# Either start new subarray or extend previous
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum
# nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Answer: 6 (subarray [4, -1, 2, 1])
Kadane's Key Insight
At each position, we decide: start a new subarray here, or extend the previous one. If the running sum becomes negative, it's better to start fresh.
Problem: Coin Change (Minimum Coins)
Find minimum coins needed to make an amount:
fn coin_change(coins: &[i32], amount: i32) -> i32 {
let amount = amount as usize;
let mut dp = vec![i32::MAX; amount + 1];
dp[0] = 0;
for i in 1..=amount {
for &coin in coins {
if coin <= i as i32 && dp[i - coin as usize] != i32::MAX {
dp[i] = dp[i].min(dp[i - coin as usize] + 1);
}
}
}
if dp[amount] == i32::MAX { -1 } else { dp[amount] }
}
// coins = [1, 2, 5], amount = 11
// dp[11] = 3 (5 + 5 + 1)
Problem: Coin Change (Number of Ways)
Count the number of ways to make an amount:
def coin_change_ways(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
# coins = [1, 2, 5], amount = 5
# Ways: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1] = 4 ways
Problem: Decode Ways
Count ways to decode a number string (A=1, B=2, ..., Z=26):
def num_decodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
prev2, prev1 = 1, 1
for i in range(1, n):
current = 0
# Single digit
if s[i] != '0':
current += prev1
# Two digits
two_digit = int(s[i-1:i+1])
if 10 <= two_digit <= 26:
current += prev2
prev2 = prev1
prev1 = current
return prev1
Problem: Word Break
Check if a string can be segmented into dictionary words:
def word_break(s, word_dict):
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # Empty string is valid
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
# s = "leetcode", wordDict = ["leet", "code"]
# dp[4] = True (leet), dp[8] = True (leetcode)
DP Problem-Solving Steps
- Define the subproblem: What does dp[i] represent?
- Find the recurrence: How does dp[i] relate to smaller subproblems?
- Identify base cases: What are dp[0], dp[1], etc.?
- Determine iteration order: Which direction to fill the table?
- Optimize space: Can we use O(1) instead of O(n)?
Common 1D DP Patterns
| Pattern | Example | Recurrence | |---------|---------|------------| | Linear | Fibonacci, Stairs | dp[i] = dp[i-1] + dp[i-2] | | Max/Min | House Robber | dp[i] = max(dp[i-1], dp[i-2] + val) | | Counting | Coin Ways | dp[i] += dp[i-coin] | | Decision | Kadane | dp[i] = max(arr[i], dp[i-1] + arr[i]) |
Key Takeaways
- DP = memoization or tabulation of overlapping subproblems
- Define what dp[i] represents clearly
- Find the recurrence relation between subproblems
- Bottom-up is often more efficient than top-down
- Space can often be optimized to O(1) for 1D DP
- Common patterns: linear DP, max/min, counting, decision
1D DP is the foundation for more complex DP problems. Master these patterns, and you'll recognize them in countless variations.