Core DP Patterns

Knapsack, longest subsequence, and matrix paths, the templates behind 80% of DP problems

Most DP problems fall into recognizable patterns. Master these templates and you'll solve new problems by recognizing which template applies.
Core patterns:1. 0/1 Knapsack, pick items to maximize value given weight constraint2. Unbounded Knapsack, items can be reused (coin change)3. Longest Common Subsequence, string matching4. Matrix/Grid paths, 2D DP

Coin Change, Unbounded Knapsackpython

def coin_change(coins, amount):
    """Minimum coins to make amount. Classic unbounded knapsack."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed for amount 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], 1 + dp[a - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 10, 25], 36))  # → 3 (25+10+1)

Longest Common Subsequencepython

def lcs(s1, s2):
    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  # Characters match
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Take the best

    return dp[m][n]

print(lcs("abcde", "ace"))  # → 3 (a, c, e)

🤔Quick Check

In coin_change, why do we loop through all amounts from 1 to target?

🎯

Phase Complete!

Dynamic Programming

You've tackled one of the hardest topics in CS. DP takes practice, keep solving problems and the patterns become second nature. Almost to the finish!

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

House Robber

Rob houses on a street, can't rob two adjacent houses. Maximize amount robbed.
Expected output: 12

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next