Dynamic Programming Patterns
Comprehensive guide to dynamic programming patterns including memoization, tabulation, common problems, and optimization techniques.
Cheat Sheet Overview
Quick reference and study metrics
Reading Time
Sections
Downloads
Category
Enhanced SEO fields
seo_title: "Dynamic Programming Cheat Sheet: Patterns & Techniques" seo_description: "Master dynamic programming with this comprehensive guide covering memoization, tabulation, classic problems, and optimization patterns for efficient algorithm design." seo_keywords: ["dynamic programming cheat sheet", "memoization techniques", "tabulation patterns", "DP problems", "optimization algorithms", "recursive solutions"] canonical_url: "https://clelandco.com/cheat-sheets/algorithm-analysis/dynamic-programming" cover_image: "/images/cheat-sheets/algorithm-analysis/dp-patterns-cover.jpg" target_audience: "Computer Science Students, Software Engineers, Competitive Programmers" content_type: "reference-guide" prerequisites: ["Recursion concepts", "Basic optimization", "Algorithm analysis"] sectionCount: 7 downloadCount: 0
Dynamic Programming
🎯 Core Principles
The Three Requirements
- Optimal Substructure: Solution can be constructed from optimal solutions of subproblems
- Overlapping Subproblems: Same subproblems appear multiple times
- Memoization Opportunity: We can store and reuse results
Key Insight: DP = Recursion + Memoization + Optimal Substructure
🔄 Top-Down vs Bottom-Up
Top-Down (Memoization)
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
Bottom-Up (Tabulation)
def fibonacci_dp(n):
if n <= 1:
return 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]
📝 Problem Recognition Patterns
Pattern 1: Decision Making
Keywords: "choose", "pick", "select", "include/exclude" Template: At each step, decide whether to include current item
# 0/1 Knapsack Pattern
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Don't include item i-1
dp[i][w] = dp[i-1][w]
# Include item i-1 if possible
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
Pattern 2: Optimal Path/Sequence
Keywords: "minimum/maximum path", "longest sequence", "edit distance" Template: Build solution by extending optimal solutions
# Longest Common Subsequence
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
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])
return dp[m][n]
Pattern 3: Counting Ways
Keywords: "number of ways", "how many ways", "count" Template: Sum all possible ways to reach each state
# Coin Change (counting ways)
def coin_change_ways(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1 # One way to make amount 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
Pattern 4: Game Theory
Keywords: "optimal play", "minimax", "both players play optimally" Template: Consider all possible moves, choose optimal
# Stone Game
def stone_game(piles):
n = len(piles)
dp = [[0] * n for _ in range(n)]
# Base case: single pile
for i in range(n):
dp[i][i] = piles[i]
# Fill for all lengths
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(piles[i] - dp[i+1][j],
piles[j] - dp[i][j-1])
return dp[0][n-1] > 0
📊 Classic Problems Comparison
Problem | Time | Space | Optimization | Pattern |
---|---|---|---|---|
Fibonacci | Rolling variables | Sequence | ||
0/1 Knapsack | 1D array | Decision | ||
LCS | Rolling array | Matching | ||
Edit Distance | Rolling array | Transform | ||
Coin Change | Natural 1D | Counting | ||
LIS | Binary search | Sequence | ||
Matrix Chain | Interval DP | Optimization |
🚀 Space Optimization Techniques
Rolling Array Technique
Before: space
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = func(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
After: space
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
curr[j] = func(prev[j], curr[j-1], prev[j-1])
prev, curr = curr, prev
In-Place Optimization (Knapsack)
Standard: space
dp = [[0] * (W + 1) for _ in range(n + 1)]
Optimized: space
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1): # Reverse order!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
🎨 State Design Patterns
Pattern 1: Index-Based States
# dp[i] = optimal solution using first i elements
def rob_houses(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
Pattern 2: Multi-Dimensional States
# dp[i][j] = optimal solution for first i items with constraint j
def knapsack_2d(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # Don't take item
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
Pattern 3: Range-Based States
# dp[i][j] = optimal solution for range [i, j]
def matrix_chain_multiplication(p):
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
🎯 Advanced Techniques
Bitmask DP
Use when: Small set of items (≤ 20), need to track subsets
def traveling_salesman(dist):
n = len(dist)
dp = {}
def solve(mask, pos):
if mask == (1 << n) - 1: # All cities visited
return dist[pos][0] # Return to start
if (mask, pos) in dp:
return dp[(mask, pos)]
ans = float('inf')
for city in range(n):
if mask & (1 << city) == 0: # City not visited
new_mask = mask | (1 << city)
ans = min(ans, dist[pos][city] + solve(new_mask, city))
dp[(mask, pos)] = ans
return ans
return solve(1, 0) # Start from city 0
Digit DP
Use when: Counting numbers with constraints
def count_numbers_with_digit_sum(n, target_sum):
s = str(n)
memo = {}
def dp(pos, sum_so_far, tight, started):
if pos == len(s):
return 1 if started and sum_so_far == target_sum else 0
if (pos, sum_so_far, tight, started) in memo:
return memo[(pos, sum_so_far, tight, started)]
limit = int(s[pos]) if tight else 9
result = 0
for digit in range(0, limit + 1):
new_tight = tight and (digit == limit)
new_started = started or (digit > 0)
new_sum = sum_so_far + digit if new_started else 0
if new_sum <= target_sum:
result += dp(pos + 1, new_sum, new_tight, new_started)
memo[(pos, sum_so_far, tight, started)] = result
return result
return dp(0, 0, True, False)
🛠️ Problem-Solving Framework
Step 1: Identify DP Signals
- Optimization: "minimum", "maximum", "optimal"
- Counting: "number of ways", "how many"
- Decision: "can we", "is it possible"
Step 2: Define State
- What information do we need to solve subproblems?
- What are the changing parameters?
Step 3: State Transition
- How do we build current state from previous states?
- What choices do we have at each step?
Step 4: Base Cases
- What are the simplest subproblems?
- What happens when parameters reach boundaries?
Step 5: Order of Computation
- Which states depend on which others?
- Can we compute in a simple loop order?
⚡ Performance Tips
When to Use DP
✅ Good for DP:
- Overlapping subproblems exist
- Optimal substructure property
- Exponential brute force can be optimized
❌ Not good for DP:
- No overlapping subproblems
- Greedy algorithm works
- Problem has special structure (graph algorithms, etc.)
Common Optimizations
- Space optimization: Use rolling arrays when possible
- Early termination: Stop when answer is found
- Pruning: Skip impossible states
- Precomputation: Calculate expensive operations once
- State compression: Use bitmasks for small sets