2D Dynamic Programming

2D Dynamic Programming - aloalgo.com

2D DP problems have states that depend on two variables. Common examples include grid traversal, string comparison (LCS, edit distance), and knapsack problems.

Use 2D DP when your state requires two changing variables:

Grid position (row, col)
Two string indices (i, j)
Item index + remaining capacity (i, capacity)

Rule of thumb: Number of changing variables = DP dimensions.

Problem: A robot starts at the top-left of an m x n grid and can only move right or down. How many unique paths exist to reach the bottom-right?

F - Function: dp[i][j] = number of paths to reach cell (i, j)
A - Arguments: row i, column j
S - Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]
T - Termination: First row and column are all 1s (only one way to reach them)

	j = 0	j = 1	j = 2	j = 3
i = 0	1	1	1	1
i = 1	1	2	3	4
i = 2	1	3	6	10
i = 3	1	4	10	20

Problem: Given two strings, find the minimum number of operations (insert, delete, replace) to convert one to the other.

F - Function: dp[i][j] = min edits to convert word1[0:i] to word2[0:j]
A - Arguments: indices i and j
S - Transition:
If chars match: 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])
T - Termination: dp[0][j] = j, dp[i][0] = i

Problem: Find the length of the longest subsequence common to two strings.

Grid Problems

Unique paths / minimum path sum
State: dp[row][col]
Transition: Usually from dp[i-1][j] and dp[i][j-1]

String Problems

Edit distance, LCS, palindrome partitioning
State: dp[i][j] for substrings/prefixes
Transition: Based on character comparison at i, j

Knapsack Problems

0/1 Knapsack, subset sum, partition equal subset
State: dp[i][capacity]
Transition: Include or exclude item i

Draw the table: Visualize the 2D grid and fill it out by hand for small inputs
Identify base cases: Usually the first row and/or column
Check iteration order: Make sure dependencies are computed before they're needed
Watch for off-by-one: String indices often need i-1 to access characters

Ready to optimize your solutions? Continue to Space Optimization for DP to learn how to reduce memory usage in your DP solutions.

Was this helpful?

Study plan All problems

Cheat Sheet

2D Dynamic Programming

When to Use 2D DP

Example: Unique Paths

Memoization (Top-Down)

Tabulation (Bottom-Up)

2D DP Table Diagram

Example: Edit Distance

Example: Longest Common Subsequence

Common 2D DP Patterns

Tips for 2D DP

Practice Problems

Next Steps

Company

Practice

Learn