Why Patterns Matter
Instead of memorising individual DP problems, recognise the pattern. Once you see which archetype a problem belongs to, the recurrence falls out naturally.
Pattern 1 — Linear DP (1D State)
State depends only on previous elements in a 1D sequence.
Example: Climbing Stairs
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Variants: House Robber, Maximum Subarray (Kadane's), Jump Game.
Pattern 2 — Grid DP (2D State)
Move through a 2D grid; state is dp[row][col].
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
for c in range(1, n):
dp[r][c] = dp[r-1][c] + dp[r][c-1]
return dp[m-1][n-1]
Variants: Minimum Path Sum, Dungeon Game.
Pattern 3 — Knapsack (Include/Exclude)
At each item, decide to include it or not. State tracks capacity or budget.
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
dp[i][w] = dp[i-1][w]
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][W]
Variants: Coin Change, Partition Equal Subset Sum, Target Sum.
Pattern 4 — Interval DP
State spans a range [i, j]. Fill shorter intervals before longer ones.
def burst_balloons(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(0, n - length):
right = left + length
for k in range(left + 1, right):
dp[left][right] = max(
dp[left][right],
nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
)
return dp[0][n-1]
Variants: Matrix Chain Multiplication, Palindrome Partitioning.
Pattern 5 — String DP (Two Sequences)
State is dp[i][j] over two strings of length i and j.
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
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
Variants: Edit Distance, Longest Common Subsequence, Regular Expression Matching.