Skip to main content

Classic DP Problems

TL;DR​

Five essential DP problems dominate interviews and real-world scenarios. 0/1 Knapsack: dp[i][w] = max value using first i items with capacity w; choose to include item or skip. Longest Common Subsequence: dp[i][j] = longest common subsequence for first i and j characters; match characters or take max of alternatives. Longest Increasing Subsequence: dp[i] = longest increasing subsequence ending at index i; extend all shorter subsequences. Coin Change: dp[i] = minimum coins to make amount i; try all coins and pick minimum. Edit Distance: dp[i][j] = minimum operations to transform first i characters to first j characters; insert, delete, or replace. All follow tabulation pattern: define state, establish recurrence, initialize base cases, fill table systematically.

Core Concepts​

The Five Classic Problems​

These problems appear frequently in interviews and algorithm competitions. Understanding their patterns helps solve variations and new problems.

Problem Classification:

  • Optimization: Knapsack, Coin Change
  • Subsequence: LCS, LIS
  • Distance: Edit Distance

Common Traits:

  • Clear state definition with 1-2 dimensions
  • Simple transitions from previous states
  • Straightforward base cases
  • Polynomial time complexity (O(n²) or O(n·m))

Knapsack Problem Variants​

The 0/1 Knapsack problem has two main interpretations:

  • Weight-centric: Given item weights and values, maximize value within weight limit
  • Capacity-centric: Given items with weights and values, select subset maximizing value

Unbounded Knapsack (variation) allows selecting same item multiple times.

String Algorithms​

LCS and Edit Distance solve classic string problems. Both use 2D DP tables where dimensions represent string lengths. Alignment concepts apply to sequence analysis, plagiarism detection, and bioinformatics.

Key Algorithms​

0/1 Knapsack Pattern​

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

Recurrence:

dp[i][w] = max(
  dp[i-1][w],                          // skip item i
  dp[i-1][w-weight[i]] + value[i]      // take item i
)

Base cases: dp[0][w] = 0 for all w (no items, no value)

LCS Pattern​

State: dp[i][j] = length of longest common subsequence for first i chars of str1 and first j chars of str2

Recurrence:

if str1[i-1] == str2[j-1]:
  dp[i][j] = dp[i-1][j-1] + 1
else:
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

LIS Pattern​

State: dp[i] = length of longest increasing subsequence ending at index i

Recurrence:

dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
dp[i] = 1 if no such j exists

Coin Change Pattern​

State: dp[i] = minimum coins needed to make amount i

Recurrence:

dp[i] = min(dp[i - coin] + 1) for all coins where coin <= i

Edit Distance Pattern​

State: dp[i][j] = minimum operations to transform first i chars of str1 to first j chars of str2

Recurrence:

if str1[i-1] == str2[j-1]:
  dp[i][j] = dp[i-1][j-1]
else:
  dp[i][j] = 1 + min(
    dp[i-1][j],      // delete from str1
    dp[i][j-1],      // insert into str1
    dp[i-1][j-1]     // replace
  )

Practical Example​

# 0/1 Knapsack Problem
def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Skip item i
            dp[i][w] = dp[i-1][w]

            # Take item i if it fits
            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]

# Longest Common Subsequence
def lcs(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[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]

# Longest Increasing Subsequence
def lis(arr):
    n = len(arr)
    # dp[i] = length of LIS ending at index i
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if n > 0 else 0

# Coin Change
def coin_change(coins, amount):
    # dp[i] = minimum coins to make amount i
    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)

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

# Edit Distance
def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: transform from/to empty string
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # delete
                    dp[i][j-1],      # insert
                    dp[i-1][j-1]     # replace
                )

    return dp[m][n]

# Tests
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 13
print(lcs("ABCDGH", "AEDFHR"))                   # 3 (ADH)
print(lis([10, 9, 2, 5, 3, 7, 101, 18]))        # 4 (2,3,7,101)
print(coin_change([1, 2, 5], 5))                # 1 (one 5-coin)
print(edit_distance("horse", "ros"))            # 3

Common Pitfalls​

warning

Incorrect state definition: Using wrong dimensions for DP table leads to index errors. Verify dimensions match problem parameters (items vs capacity, string lengths, etc.).

Off-by-one in recurrence: When accessing arr[i-1] from dp[i], ensure indexing is consistent. String and array indices need careful handling.

Forgetting base cases: Incomplete initialization leaves undefined states. For 2D problems, initialize full first row and column.

Unbounded vs 0/1 confusion: Knapsack variations require different recurrence. Unbounded allows reusing items; 0/1 does not.

Inefficient LIS implementation: O(n²) is standard for simple version but can optimize to O(n log n) with binary search and patience sorting.

Not tracking actual solution: DP computes optimal value but not the choices. If solution reconstruction needed, track parent pointers.

Self-Check​

  1. Why does 0/1 Knapsack require 2D DP while Coin Change uses 1D? What's the key difference?
  2. How would you reconstruct the actual longest common subsequence string, not just its length?
  3. For Longest Increasing Subsequence, why is LIS ending at each position a useful state definition?

One Takeaway​

info

Classic DP problems share a common pattern: define state to represent subproblem, establish recurrence relating state to smaller subproblems, initialize base cases, and fill table systematically. Master these five problems and you'll recognize similar patterns in new problems. The key insight is choosing the right state—once you have that, the recurrence usually becomes obvious. Practice reconstructing solutions from DP tables to develop intuition for DP state transitions.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.