Dynamic Programming — Memoization & Tabulation Guide
Dynamic Programming (DP) is an optimization technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result for future use. It applies when a problem has optimal substructure and overlapping subproblems.
What You'll Learn
You will learn the two DP approaches — top-down memoization and bottom-up tabulation — and common DP patterns including Fibonacci, knapsack, longest common subsequence, and grid paths.
Why It Matters
DP transforms exponential-time brute-force solutions into polynomial-time algorithms. It's essential for optimization problems in resource allocation, bioinformatics (DNA sequence alignment), and pathfinding.
Real-World Use
Durga Antivirus Pro uses DP for virus signature matching. The longest common subsequence algorithm identifies similarities between file byte sequences and known malware patterns, even when the malware has been mutated to avoid detection.
Fibonacci: The Classic DP Example
graph TD
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3["fib(3)"]
F4 --> F3b["fib(3)"]
F4 --> F2["fib(2)"]
F3 --> F2b["fib(2)"]
F3 --> F1["fib(1)"]
F3b --> F2c["fib(2)"]
F3b --> F1b["fib(1)"]
style F5 fill:#4a90d9,stroke:#333,color:#fff
style F3 fill:#e67e22,stroke:#333,color:#fff
style F3b fill:#e67e22,stroke:#333,color:#fff
Without DP, fib(3) is computed twice. DP stores results so each subproblem is solved only once.
Top-Down (Memoization)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print("fib(50):", fib_memo(50))
Expected output:
fib(50): 12586269025
function fibMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.log("fib(50):", fibMemo(50));
Expected output:
fib(50): 12586269025
Bottom-Up (Tabulation)
def fib_tab(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]
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
print("Tabulation fib(50):", fib_tab(50))
print("Optimized fib(50):", fib_optimized(50))
Expected output:
Tabulation fib(50): 12586269025
Optimized fib(50): 12586269025
0/1 Knapsack Problem
Given items with weights and values, maximize value without exceeding capacity. Each item can be taken at most once:
def knapsack_01(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):
if weights[i - 1] <= w:
dp[i][w] = max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
)
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print("Max value:", knapsack_01(weights, values, 5))
Expected output:
Max value: 7
function knapsack01(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({length: n + 1}, () => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
values[i - 1] + dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]
);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
console.log("Max value:", knapsack01([2, 3, 4, 5], [3, 4, 5, 6], 5));
Expected output:
Max value: 7
Longest Common Subsequence (LCS)
Finds the longest sequence that appears in the same order in both strings:
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]
def reconstruct_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])
lcs_str = []
i, j = m, n
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
lcs_str.append(text1[i - 1])
i -= 1; j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs_str))
text1, text2 = "ABCBDAB", "BDCAB"
print("LCS length:", lcs(text1, text2))
print("LCS string:", reconstruct_lcs(text1, text2))
Expected output:
LCS length: 4
LCS string: BCAB
Common DP Patterns
| Pattern | Example | Approach |
|---|---|---|
| Fibonacci | Climbing stairs | dp[i] = dp[i-1] + dp[i-2] |
| 0/1 Knapsack | Subset sum | dp[i][w] = max(val + dp[i-1][w-wt], dp[i-1][w]) |
| Unbounded Knapsack | Coin change | dp[i] = min(dp[i], dp[i-coin] + 1) |
| LCS | Edit distance | Match or skip one character |
| Grid | Unique paths | Sum of top and left cells |
Time Optimization Tips
# 1D DP for knapsack (space optimization)
def knapsack_1d(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
return dp[capacity]
Common Pitfalls
1. Not Recognizing Overlapping Subproblems
If subproblems don't overlap, DP offers no benefit over divide-and-conquer. Verify subproblem reuse before using DP.
2. Wrong DP Array Dimensions
Define the DP table based on the number of state variables. For knapsack with n items and capacity C, the table is (n+1) × (C+1).
3. Off-by-One in DP Table Indices
DP tables often pad with an extra row/column for base cases. Accessing dp[i-1][j-1] when i or j is 0 reads the padded row/column.
4. Mutable Default Argument in Memoization
memo={} in Python function defaults persists across calls. Use None and initialize inside the function:
# Wrong: memo shared across calls
def fib(n, memo={}):
...
# Correct
def fib(n, memo=None):
if memo is None:
memo = {}
...
5. Not Testing Base Cases
Empty strings, zero capacity, and single-element inputs should produce correct results. Always test edge cases.
Practice Questions
1. Coin change: find the minimum number of coins needed to make a given amount.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 2, 5], 11))
Expected output: 3
2. Longest increasing subsequence (LIS).
3. Edit distance (Levenshtein distance) between two strings.
4. Challenge: Given a grid with obstacles, find the number of unique paths from top-left to bottom-right moving only right and down.
5. Real-world task: Durga Antivirus Pro's pattern matching engine uses DP to compare byte sequences. Write a function that computes the edit distance between a file's byte sequence and a known malware signature, identifying files that are similar but not identical to known threats.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro