Overview

Many problems need two numbers to describe a subproblem: a position in two different strings, a row and a column of a grid, or an item index and a remaining capacity. The table becomes two-dimensional, but the method is unchanged — define the state, find the recurrence from the last decision, set base cases, and fill the table in a valid order.

Three families cover most interview questions. Grid DP counts or optimises paths. Two-sequence DP compares strings character by character (LCS, edit distance). Knapsack DP decides, for each item, whether to take it given a budget — and with the right loop direction its table compresses to one dimension.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Grid / two-sequence DPO(m · n) time, O(min(m, n)) space possible
0/1 knapsackO(n · capacity)
Interval DPO(n³) typically

Patterns to recognise

Paths in a grid

Use it for: Unique paths, minimum path sum, dungeon game.

Fill row by row; the first row and column are base cases.

Compare two strings

Use it for: LCS, edit distance, distinct subsequences.

Table of size (m + 1) × (n + 1) with empty-prefix base cases.

Subset sum / knapsack

Use it for: Partition equal subset sum, target sum, coin change II.

dp[c] = whether (or how many ways) capacity c can be reached; mind the loop direction.

Code template

Edit distance
def min_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                 # delete everything
    for j in range(n + 1):
        dp[0][j] = j                 # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[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]

Common mistakes

  • Off-by-one between table indices (prefix length) and string indices (i − 1).
  • Iterating knapsack capacity in the wrong direction silently switches between 0/1 and unbounded.
  • Allocating a full 2D table when only the previous row is needed can exceed memory limits.

Quick check

Three questions on DP 2D. Get all three right to earn +15 XP.

  1. Unique paths in an m x n grid, moving only right or down: dp[r][c] equals:

  2. The standard longest common subsequence table for strings of length m and n takes:

  3. In 0/1 knapsack with a 1D array, why iterate capacity from high to low?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on DP 2D?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor