A
AiTechWorlds
AiTechWorlds
University learning companion
Algorithms · Classic DP Problems: Fibonacci, Knapsack, LCS
Use this course-level map to place “Classic DP Problems: Fibonacci, Knapsack, LCS” in the larger system. It complements—not replaces—a topic-specific worked diagram.
Classic dynamic programming (DP) problems knapsack, longest common subsequence, coin change share one trait: an optimal solution is built from optimal solutions to smaller overlapping subproblems.
You're preparing for a mountain trek with a backpack that can hold at most 10 kg. At the trailhead, there's a supply cache with five items. Each has a weight and a value (in terms of how much it helps your survival). You can only take each item once you can't split them.
| Item | Weight | Value |
|---|---|---|
| First Aid Kit | 2 kg | $6 |
| Water Purifier | 3 kg | $10 |
| Thermal Blanket | 4 kg | $12 |
| Navigation Device | 5 kg | $15 |
| Emergency Rations | 7 kg | $20 |
How do you maximize value within your weight limit? You can't just take the most valuable item (rations at 7 kg) because that wastes 3 kg of capacity. You can't take "a bit of each." You need to find the optimal combination.
This is the 0/1 Knapsack Problem and it's one of the most famous problems in computer science.
Your first instinct might be: "take the best value per weight item first." Let's try:
Greedy picks: Water Purifier (3 kg) + Navigation Device (5 kg) + Thermal Blanket left over (2 kg left, Blanket needs 4 doesn't fit) = $25 total.
But the optimal solution is: Water Purifier (3 kg) + Thermal Blanket (4 kg) + First Aid Kit (2 kg) = 9 kg = $28 total.
Greedy fails. We need DP.
State definition: dp[i][w] = maximum value using first i items with weight capacity w
Recurrence:
dp[i][w] = dp[i-1][w]dp[i][w] = dp[i-1][w - weight[i]] + value[i]def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = max value with first i items and capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1): # For each item
for w in range(capacity + 1): # For each possible capacity
# Option 1: Don't take item i
dp[i][w] = dp[i-1][w]
# Option 2: Take item i (only if it fits)
if weights[i-1] <= w:
take_value = dp[i-1][w - weights[i-1]] + values[i-1]
dp[i][w] = max(dp[i][w], take_value)
return dp[n][capacity]
# --- Our hiking example ---
weights = [2, 3, 4, 5, 7]
values = [6, 10, 12, 15, 20]
capacity = 10
result = knapsack(weights, values, capacity)
print(f"Maximum value: ${result}")Output:
Maximum value: $28Partial DP table visualization (rows = items, columns = capacity 0-10):
Cap: 0 1 2 3 4 5 6 7 8 9 10
No items: 0 0 0 0 0 0 0 0 0 0 0
+FirstAid: 0 0 6 6 6 6 6 6 6 6 6
+WaterPur: 0 0 6 10 10 16 16 16 16 16 16
+Blanket: 0 0 6 10 12 16 18 22 22 28 28
+NavDev: 0 0 6 10 12 16 18 22 25 28 28
+Rations: 0 0 6 10 12 16 18 22 25 28 28The answer $28 appears at dp[5][10].
LCS appears everywhere:
Definition: A subsequence maintains relative order but doesn't need to be contiguous. "ACE" is a subsequence of "ABCDE" skip B and D.
Problem: Given strings "ABCBDAB" and "BDCAB", find their longest common subsequence.
def lcs(s1, s2):
m, n = len(s1), len(s2)
# dp[i][j] = LCS length of s1[:i] and s2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # Characters match!
dp[i][j] = dp[i-1][j-1] + 1 # Extend the LCS by 1
else: # No match
dp[i][j] = max(dp[i-1][j], # Skip char from s1
dp[i][j-1]) # Skip char from s2
return dp[m][n]
def lcs_string(s1, s2):
"""Reconstruct the actual LCS string (not just length)."""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Trace back through the table to reconstruct the sequence
result = []
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
result.append(s1[i-1]) # This character is part of LCS
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1 # Move up
else:
j -= 1 # Move left
return ''.join(reversed(result))
# --- Example ---
s1 = "ABCBDAB"
s2 = "BDCAB"
print(f"LCS length: {lcs(s1, s2)}")
print(f"LCS string: {lcs_string(s1, s2)}")Output:
LCS length: 4
LCS string: BCABDP table for "ABCBDAB" vs "BDCAB":
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4 ← LCS length = 4Problem: Given coin denominations and a target amount, find the minimum number of coins to make that amount.
Example: Coins = [1, 5, 6, 9], Amount = 11
You might guess: 9 + 1 + 1 = 3 coins. But the optimal is: 6 + 5 = 2 coins.
def coin_change(coins, amount):
# dp[i] = minimum coins needed to make amount i
# Initialize with infinity (impossible state)
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins to make amount 0
for i in range(1, amount + 1): # For each amount from 1 to target
for coin in coins: # Try each coin denomination
if coin <= i: # Coin fits (doesn't exceed amount)
dp[i] = min(dp[i], dp[i - coin] + 1) # 1 coin + best for remainder
return dp[amount] if dp[amount] != float('inf') else -1
# --- Example with trace ---
coins = [1, 5, 6, 9]
amount = 11
result = coin_change(coins, amount)
print(f"Minimum coins for {amount}: {result}")
# Show the full dp table
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
print("DP table:", dp)Output:
Minimum coins for 11: 2
DP table: [0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 2]Table trace for coins=[1,5,6,9], amount=11:
Amount: 0 1 2 3 4 5 6 7 8 9 10 11
Coins: 0 1 2 3 4 1 1 2 3 1 2 2
↑ ↑ ↑ ↑
base 5 6 9 (single coins)
11 = 6+5 = 2 coinsStep 1 Recognize the pattern: Does the problem ask for max/min/count/possible? Do subproblems repeat?
Step 2 Define the state clearly:
dp[i][w] = max value with i items and capacity wdp[i][j] = LCS of first i chars of s1 and first j chars of s2dp[i] = min coins to make amount iStep 3 Write the recurrence:
Step 4 Set base cases:
dp[0][w] = 0 (no items → no value)dp[i][0] = dp[0][j] = 0 (empty string → LCS length 0)dp[0] = 0 (no coins to make amount 0)| Problem Type | State | Recurrence Pattern |
|---|---|---|
| 0/1 Knapsack | dp[i][w] | take / don't take item |
| Unbounded Knapsack | dp[w] | use item multiple times |
| LCS | dp[i][j] | match chars or skip one string |
| Edit Distance | dp[i][j] | insert / delete / replace |
| Coin Change (min) | dp[amount] | try each coin, take min |
| Coin Change (count) | dp[amount] | sum of ways using each coin |
| Longest Increasing Subseq. | dp[i] | extend previous valid subsequences |
| Matrix Chain Multiply | dp[i][j] | optimal split point |
These three problems Knapsack, LCS, and Coin Change appear regularly in technical interviews and are the foundation for understanding dozens of more complex DP problems. Master these, and the framework transfers directly to:
The insight is always the same: define the state precisely, find the recurrence, trust the table.
University learning companion
Algorithms · Classic DP Problems: Fibonacci, Knapsack, LCS
Complete the steps without looking at the answer first; record evidence rather than only a final result.
These are primary or established learning references for this subject. Check the relevant chapter or specification for the exact topic and version.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises