2D Dynamic Programming — Complete Guide

What is 2D DP?

2D DP uses a 2D table dp[i][j] where the state depends on two parameters — typically two strings, a 2D grid, or an interval [i,j].

The 7 Core 2D DP Patterns

Pattern 1 — LCS / Sequence Alignment

Two strings s1, s2. dp[i][j] = answer for s1[:i], s2[:j].

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])

Problems: LCS, Longest Common Substring, Shortest Common Supersequence

Pattern 2 — Edit Distance / String Transform

Cost to transform s1 to s2.

if s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Problems: Edit Distance, Delete Operations, Min ASCII Delete Sum

Pattern 3 — Grid Path Counting

Paths through a grid from (0,0) to (m-1,n-1).

dp[i][j] = dp[i-1][j] + dp[i][j-1]  (if not obstacle)

Problems: Unique Paths, Unique Paths II, Minimum Path Sum

Pattern 4 — Interval DP

Optimal over all split points in interval [i,j].

dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost) for k in [i,j-1]

Problems: Burst Balloons, Matrix Chain, Minimum Cost Tree

Pattern 5 — 2D Knapsack / Constraints

Items with two attributes (weight + volume), or 0/1 knapsack on 2D.

dp[i][j][k] = best using i items with constraints j, k

Problems: Ones and Zeroes, Last Stone Weight II

Pattern 6 — Stock Trading DP

State = (day, holding, transactions_left).

hold[i] = max(hold[i-1], -prices[i])
cash[i] = max(cash[i-1], hold[i-1] + prices[i])

Problems: Best Time to Buy/Sell (all variants)

Pattern 7 — DP on Grid with State

State includes position AND extra state (broken obstacles, remaining turns).

dp[i][j][k] = best at (i,j) with k remaining

Problems: Dungeon Game, Cherry Pickup, Minimum Falling Path

5-Language Templates

LCS Template

# Python
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])

Edit Distance Template

# Python
dp = [[0]*(n+1) for _ in range(m+1)]
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 s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1]
        else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Problem Index