2D Dynamic Programming — Master Recap & Cheatsheet

2D DP Master Cheatsheet

Pattern Reference

Pattern	State	Transition	Example
LCS	dp[i][j] = LCS of s1[:i], s2[:j]	match+1 or max(skip)	LCS
Edit Distance	dp[i][j] = min ops	1+min(ins,del,rep)	Edit Distance
Grid Paths	dp[i][j] = paths to cell	dp[i-1][j]+dp[i][j-1]	Unique Paths
Grid Min/Max	dp[i][j] = best cost	min/max from prev row	Min Path Sum
Interval DP	dp[i][j] = best for [i,j]	split at k, recurse	Burst Balloons
Stock DP	buy/sell state	update states daily	Stock variants
2D Knapsack	dp[i][j] = best with i,j capacity	0/1 bwd update	Ones & Zeroes

Stock State Machine

# Most general form (cooldown example)
hold = max(hold, rest - price)
sold = hold + price
rest = max(rest, sold_prev)

Interval DP Template

# Fill by increasing length
for length in range(2, n+1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = INF
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,j,k))

LCS Reconstruction

# Backtrack to reconstruct LCS string
i, j = m, n
while i > 0 and j > 0:
    if s1[i-1] == s2[j-1]:
        result.append(s1[i-1]); i -= 1; j -= 1
    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1

Problem Index

Grid Paths: Unique Paths (01,02), Min Path Sum (03), Triangle (04)

LCS: LCS (05), SCS (07), Edit Distance (06), Delete Ops (part of LCS family)

Stock: All 6 variants covered (09-14)

Interval DP: Burst Balloons (08), Strange Printer (21)

2D Knapsack: Ones and Zeroes (19)

Grid with State: Dungeon Game (18), Falling Path (20)

String Matching: Interleave (15), Regex (16), Wildcard (17)