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.

Problem 1: 0/1 Knapsack

Why Not Greedy?

Your first instinct might be: "take the best value-per-weight item first." Let's try:

Water Purifier: $10 / 3 kg = $3.33/kg (best ratio)
Navigation Device: $15 / 5 kg = $3.00/kg
Thermal Blanket: $12 / 4 kg = $3.00/kg

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.

Building the DP Table

State definition: dp[i][w] = maximum value using first i items with weight capacity w

Recurrence:

If we don't take item i: dp[i][w] = dp[i-1][w]
If we do take item i: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
Choose the maximum of these two options

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: $28

Partial 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  28

The answer $28 appears at dp[5][10].

Problem 2: Longest Common Subsequence (LCS)

Real-World Applications

LCS appears everywhere:

Git diff — finding what changed between two versions of a file
DNA analysis — comparing genetic sequences to find mutations
Plagiarism detection — finding common sequences in documents
Spell checkers — computing edit distance

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: BCAB

DP 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 = 4

Problem 3: Coin Change

Problem: 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 coins

How to Approach Any DP Problem

Step 1 — Recognize the pattern: Does the problem ask for max/min/count/possible? Do subproblems repeat?

Step 2 — Define the state clearly:

Knapsack: dp[i][w] = max value with i items and capacity w
LCS: dp[i][j] = LCS of first i chars of s1 and first j chars of s2
Coin Change: dp[i] = min coins to make amount i

Step 3 — Write the recurrence:

Knapsack: take or don't take item i
LCS: characters match → extend; don't match → best of skipping either
Coin Change: try each coin, take minimum

Step 4 — Set base cases:

Knapsack: dp[0][w] = 0 (no items → no value)
LCS: dp[i][0] = dp[0][j] = 0 (empty string → LCS length 0)
Coin Change: dp[0] = 0 (no coins to make amount 0)

Problem Type to DP Pattern

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

Interview Relevance

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:

Rod Cutting (variant of Knapsack)
Edit Distance (variant of LCS)
Partition Equal Subset Sum (Knapsack recognition)
Word Break (Coin Change recognition)

The insight is always the same: define the state precisely, find the recurrence, trust the table.

💬 DiscussionPowered by GitHub Discussions

📱

Get this course's notes on Telegram!

Free cheat sheets, summaries & practice exercises

Get Notes Free →

40 minLesson 13 of 17

Course Contents(17 lessons)

▾

Chapter 1: What Is an Algorithm?

Algorithms: The Recipes of Computing20 min

Big O and Algorithm Complexity Analysis35 min

Chapter 2: Recursion

Recursion: Functions That Call Themselves30 min

Backtracking: Exploring All Possibilities32 min

Chapter 3: Sorting Algorithms

Bubble Sort and Selection Sort Explained28 min

Insertion Sort and Its Practical Applications25 min

Merge Sort: Divide and Conquer35 min

Quick Sort: The Workhorse of Sorting35 min

Sorting Algorithm Comparison and When to Use Each22 min

Chapter 4: Searching Algorithms

Linear Search vs Binary Search25 min

Binary Search Variations and Applications28 min

Chapter 5: Dynamic Programming

Dynamic Programming: Memoizing Subproblems35 min

Classic DP Problems: Fibonacci, Knapsack, LCS40 min

Chapter 6: Graph Algorithms

BFS and DFS: Graph Search Strategies35 min

Dijkstra's Algorithm: Shortest Path38 min

Chapter 7: Greedy Algorithms + Final Project

Greedy Algorithms: Locally Optimal Choices28 min

Final Project: Algorithm Design Challenge45 min

Chapter 5: Dynamic Programming

Classic DP Problems: Fibonacci, Knapsack, LCS

Lesson 4: Classic Dynamic Programming Problems

The Hiker's Dilemma

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

This is the 0/1 Knapsack Problem — and it's one of the most famous problems in computer science.

Problem 1: 0/1 Knapsack

Why Not Greedy?

Your first instinct might be: "take the best value-per-weight item first." Let's try:

Water Purifier: $10 / 3 kg = $3.33/kg (best ratio)
Navigation Device: $15 / 5 kg = $3.00/kg
Thermal Blanket: $12 / 4 kg = $3.00/kg

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.

Building the DP Table

State definition: dp[i][w] = maximum value using first i items with weight capacity w

Recurrence:

If we don't take item i: dp[i][w] = dp[i-1][w]
If we do take item i: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
Choose the maximum of these two options

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: $28

Partial 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  28

The answer $28 appears at dp[5][10].

Problem 2: Longest Common Subsequence (LCS)

Real-World Applications

LCS appears everywhere:

Git diff — finding what changed between two versions of a file
DNA analysis — comparing genetic sequences to find mutations
Plagiarism detection — finding common sequences in documents
Spell checkers — computing edit distance

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: BCAB

DP 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 = 4

Problem 3: Coin Change

Problem: 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 coins

How to Approach Any DP Problem

Step 1 — Recognize the pattern: Does the problem ask for max/min/count/possible? Do subproblems repeat?

Step 2 — Define the state clearly:

Knapsack: dp[i][w] = max value with i items and capacity w
LCS: dp[i][j] = LCS of first i chars of s1 and first j chars of s2
Coin Change: dp[i] = min coins to make amount i

Step 3 — Write the recurrence:

Knapsack: take or don't take item i
LCS: characters match → extend; don't match → best of skipping either
Coin Change: try each coin, take minimum

Step 4 — Set base cases:

Knapsack: dp[0][w] = 0 (no items → no value)
LCS: dp[i][0] = dp[0][j] = 0 (empty string → LCS length 0)
Coin Change: dp[0] = 0 (no coins to make amount 0)

Problem Type to DP Pattern

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

Interview Relevance

Rod Cutting (variant of Knapsack)
Edit Distance (variant of LCS)
Partition Equal Subset Sum (Knapsack recognition)
Word Break (Coin Change recognition)

The insight is always the same: define the state precisely, find the recurrence, trust the table.

💬 DiscussionPowered by GitHub Discussions

📱

Get this course's notes on Telegram!

Free cheat sheets, summaries & practice exercises

Get Notes Free →