2D Dynamic Programming Interview Patterns (2025)
Two-dimensional DP problems are common at Google, Meta, Amazon, and Microsoft. They involve grids, two-sequence comparisons, or interval-based problems. Mastering 2D DP unlocks a large category of medium and hard LeetCode problems.
Pattern 1: Grid Traversal DP
# Unique Paths (LeetCode 62) - count paths from top-left to bottom-right
def uniquePaths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Time O(mn), Space O(mn) -> optimize to O(n) with 1D array
# Minimum Path Sum (LeetCode 64)
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]Pattern 2: Two-Sequence DP
# Longest Common Subsequence (LeetCode 1143)
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[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]
# Edit Distance (LeetCode 72)
def minDistance(word1, word2):
m, n = len(word1), len(word2)
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 word1[i-1] == word2[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]Pattern 3: Interval DP
Interval DP fills a table where dp[i][j] represents the answer for a subproblem on range [i, j]. Process by increasing interval length.
# Minimum Cost to Merge Stones / Burst Balloons pattern
# Burst Balloons (LeetCode 312)
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in range(n)]
# dp[i][j] = max coins from bursting all balloons between i and j (exclusive)
for length in range(2, n):
for i in range(n - length):
j = i + length
for k in range(i+1, j):
dp[i][j] = max(dp[i][j],
dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])
return dp[0][n-1]
# Palindrome Partitioning II (LeetCode 132) - min cuts
def minCut(s):
n = len(s)
# Precompute palindrome table
is_pal = [[False]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or is_pal[i+1][j-1]):
is_pal[i][j] = True
# dp[i] = min cuts for s[:i+1]
dp = list(range(-1, n))
for i in range(n):
for j in range(i+1):
if is_pal[j][i]:
dp[i+1] = min(dp[i+1], dp[j] + 1)
return dp[n]Pattern 4: Knapsack Variants
# 0/1 Knapsack: each item used at most once
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(capacity+1):
dp[i][w] = dp[i-1][w] # don't take item i
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]
# Unbounded Knapsack: each item used unlimited times
def knapsack_unbounded(weights, values, capacity):
dp = [0] * (capacity + 1)
for w in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# Coin Change (LeetCode 322) - unbounded knapsack variant
def coinChange(coins, amount):
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 -1Pattern 5: Stock Problems (State Machine DP)
# Best Time to Buy and Sell Stock with Cooldown (LeetCode 309)
def maxProfit_cooldown(prices):
hold = -float('inf') # max profit while holding a stock
sold = 0 # max profit day after selling (cooldown)
rest = 0 # max profit while resting (not holding, not cooldown)
for price in prices:
prev_hold, prev_sold, prev_rest = hold, sold, rest
hold = max(prev_hold, prev_rest - price) # buy from rest state
sold = prev_hold + price # sell today
rest = max(prev_rest, prev_sold) # rest or come from sold
return max(sold, rest)
# Stock with at most K transactions (LeetCode 188)
def maxProfit_k(k, prices):
n = len(prices)
if not prices or k == 0: return 0
if k >= n // 2: # can make unlimited transactions
return sum(max(prices[i+1]-prices[i], 0) for i in range(n-1))
dp = [[0]*n for _ in range(k+1)]
for t in range(1, k+1):
max_sofar = -prices[0]
for i in range(1, n):
dp[t][i] = max(dp[t][i-1], prices[i] + max_sofar)
max_sofar = max(max_sofar, dp[t-1][i] - prices[i])
return dp[k][n-1]Pattern 6: Matrix Chain / Tree DP in 2D
# Maximal Square (LeetCode 221)
def maximalSquare(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0]*n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
# Largest Rectangle in Histogram (LeetCode 84) - used in maximalRectangle
def largestRectangleArea(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaKey Problems to Practice
- LeetCode 62, 63, 64 – Unique paths and minimum path sum (grid DP)
- LeetCode 1143 – Longest common subsequence
- LeetCode 72 – Edit distance
- LeetCode 312 – Burst balloons (interval DP)
- LeetCode 322, 518 – Coin change (knapsack)
- LeetCode 309, 188 – Stock problems (state machine)
- LeetCode 221 – Maximal square
- LeetCode 85 – Maximal rectangle (histogram approach)