Step 1 Understand it
Remember it by
Two inputs or a grid? dp[i][j] = the answer for the first i of one and the first j of the other.
Watch it happen
Read the animation as text
- Count the paths from the top-left to the bottom-right of a 3 × 3 grid, moving only right or down. Each cell will hold the number of paths that reach it.
- The top row and the left column can each be reached only one way (straight along the edge): 1.
- Cell (1,1): you arrive from above (1 path) or from the left (1 path): 1 + 1 = 2.
- Cell (1,2): you arrive from above (1 path) or from the left (2 paths): 1 + 2 = 3.
- Cell (2,1): you arrive from above (2 paths) or from the left (1 path): 2 + 1 = 3.
- Cell (2,2): you arrive from above (3 paths) or from the left (3 paths): 3 + 3 = 6.
- Answer: 6 paths. Each cell is filled once from two saved neighbours: O(m × n).
The idea
When the state needs two numbers (positions in two strings, or a cell in a grid), the table is 2-D. Each cell is filled from neighbours already filled: up, left, or the diagonal.
Picture it
block-beta columns 3 a["1"] b["1"] c["1"] d["1"] e["2"] f["3"] g["1"] h["3"] i["6"] style i fill:#2a6f97,color:#fff
Analogy
Filling in a mileage table between towns, where each entry can be worked out from entries you've already written above and to the left.
Where the analogy breaks
A mileage table is symmetric and finished. A DP table is filled in a strict order, and the order is chosen so that every cell's inputs already exist.
More detail
What it is
2-D DP is the exact same concept as 1-D DP, but your 'state' depends on TWO variables instead of one. Imagine you are navigating a grid from the top-left to the bottom-right. The number of ways to reach a specific cell depends on the cell *above* it AND the cell to its *left*. Therefore, instead of a 1D array to remember answers, you need a full 2D array (a matrix)!
When to use it
- When dealing with grids or matrices (e.g., 'Unique Paths' or 'Longest Common Subsequence').
- When the subproblem state requires tracking two distinct indices simultaneously (like taking items from Two different strings at the same time).
- When dealing with classic Knapsack problems.
How it works
You create a int[][] dp = new int[rows][cols]. You carefully initialize the base cases—often the first row and the first column. Then, you use nested for-loops to iterate through every cell. For each cell, the answer is calculated by looking at the immediately neighboring cells that have ALREADY been computed (e.g., dp[r][c] = dp[r-1][c] + dp[r][c-1]).
Example walkthrough
Input: grid 2x2. Find paths from 0,0 to 1,1. Right/Down only.
- Create 2x2 DP matrix.
- Initialize first row to 1 (only 1 way to go straight right).
- Initialize first col to 1 (only 1 way to go straight down).
- Calculate cell (1,1). It's the sum of the cell above (1) and left (1). Thus dp[1][1] = 2.
- Target cell is 2. Return 2!
Result: 2
Related patterns
- 1-D Dynamic Programming: Literally the exact same thing but with an extra inner loop.
Step 2 Recognise it
Words that signal it
- Two strings: 'longest common', 'edit distance', 'interleaving', 'distinct subsequences', 'matching'
- A grid where you only move right/down: 'unique paths', 'minimum path sum'
- Knapsack: items × capacity ('coin change II', 'target sum')
Don't confuse it with
- 1-D DP: If the answer depends on one position, 1-D is enough. Two strings, or position plus capacity, needs 2-D.
- Graphs: Free movement in any direction → graph search. Only right/down → DP.
Gut check
Does the sub-question need two indexes? → 2-D DP table.
How to recognise it in an interview
The problem literally gives you a 2D grid, asks you to compare TWO different strings, or presents a 'Knapsack' choice.
Step 3 The template
The general shape. Adapt it to each problem rather than learning one solution per problem.
def solve(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # row/col 0 = empty prefix
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # use the diagonal
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # up or left
return dp[m][n]The same template in Java
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// Fill the first row
for (int i = 0; i < n; i++) dp[0][i] = 1;
// Fill the first col
for (int i = 0; i < m; i++) dp[i][0] = 1;
// Fill the rest of the matrix
for (int r = 1; r < m; r++) {
for (int c = 1; c < n; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
}
return dp[m - 1][n - 1];
}
}Common mistakes
- Off-by-one between string indexes and table indexes (dp has an extra row and column for the empty prefix).
- Filling cells before their inputs are ready.
- Forgetting the first row and column (base cases).
Step 4 Watch it run
Two problems, traced step by step exactly as the code runs.
Easy example: Unique Paths
Input: m = 3, n = 3 (move only right or down)
| cell | how | paths |
|---|---|---|
| (1,1) | from above 1 + from left 1 | 2 |
| (1,2) | from above 1 + from left 2 | 3 |
| (2,1) | from above 2 + from left 1 | 3 |
| (2,2) | from above 3 + from left 3 | 6 |
Result: 6
Notice: The first row and column are all 1 (only one way to go straight). Every other cell adds the one above and the one to the left.
def unique_paths(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j - 1] # above (old row[j]) + left (row[j - 1])
return row[-1]Medium example: Longest Common Subsequence
Input: text1 = 'abcde', text2 = 'ace'
| prefixes compared | rule | LCS length |
|---|---|---|
| 'a' vs 'a' | 'a' = 'a' → diagonal 0 + 1 | 1 |
| 'a' vs 'ace' | 'a' ≠ 'e' → max(up 0, left 1) | 1 |
| 'ab' vs 'ace' | 'b' ≠ 'e' → max(up 1, left 1) | 1 |
| 'abc' vs 'ac' | 'c' = 'c' → diagonal 1 + 1 | 2 |
| 'abc' vs 'ace' | 'c' ≠ 'e' → max(up 1, left 2) | 2 |
| 'abcd' vs 'ace' | 'd' ≠ 'e' → max(up 2, left 2) | 2 |
| 'abcde' vs 'ace' | 'e' = 'e' → diagonal 2 + 1 | 3 |
Result: 3
Notice: Matching letters extend the diagonal answer by 1; otherwise you drop a letter from one string or the other and keep the better result.
def longest_common_subsequence(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[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]Step 5 Practise
Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.
Medium
-
Unique Paths Medium
Count the paths from the top-left to the bottom-right of a grid moving only right or down.
Show answer
Technique: 2-D DP on a grid
The clue: Only right and down moves, count the paths.
The trick: paths(r, c) = paths(r − 1, c) + paths(r, c − 1); the first row and column are 1.
-
Longest Common Subsequence Medium
Find the length of the longest subsequence shared by two strings.
Show answer
Technique: 2-D DP on two strings
The clue: Two strings + 'longest common'.
The trick: Same letter → diagonal + 1; otherwise max(up, left).
-
Trade as many times as you like, but after selling you must wait a day; maximise profit.
Show answer
Technique: DP with states (holding / sold / resting)
The clue: Each day's choice depends on what state you're in.
The trick: Track the best profit for each state each day; selling leads to a forced rest day.
-
Coin Change II Medium
Count the combinations of coins that make an amount.
Show answer
Technique: Unbounded knapsack DP (coins outer loop)
The clue: 'Number of combinations' (order doesn't matter).
The trick: Loop coins on the outside and amounts inside, so each combination is counted once: dp[a] += dp[a − c].
-
Target Sum Medium
Put + or − before each number; count the ways to reach the target.
Show answer
Technique: DP over (index, sum) / knapsack
The clue: 'Number of ways' with two choices per number.
The trick: Count ways with a map from sum → ways, updated for each number (or convert to a subset-sum count).
-
Interleaving String Medium
Decide whether s3 is formed by interleaving s1 and s2 while keeping each one's order.
Show answer
Technique: 2-D DP on two strings
The clue: Two strings consumed in order, with choices at each step.
The trick: dp[i][j] is true if s3's next character matches s1[i] with dp[i + 1][j] true, or s2[j] with dp[i][j + 1] true.
-
Edit Distance Medium
Find the fewest inserts, deletes and replacements to turn one word into another.
Show answer
Technique: 2-D DP on two strings
The clue: Two strings + minimum operations.
The trick: Same letter → diagonal; otherwise 1 + min(insert, delete, replace) from the three neighbours.
Hard
-
Find the longest strictly increasing path in a grid (four directions).
Show answer
Technique: DFS + memoisation
The clue: Paths in any direction, but 'increasing' means no cycles.
The trick: DFS from every cell, caching the longest path from each cell.
-
Count the ways string t appears as a subsequence of s.
Show answer
Technique: 2-D DP on two strings
The clue: Two strings + 'how many ways'.
The trick: If s[i] = t[j]: use it (i + 1, j + 1) or skip it (i + 1, j); otherwise skip it.
-
Burst Balloons Hard
Burst balloons for coins (left × self × right); maximise the total.
Show answer
Technique: Interval DP (the last balloon to burst)
The clue: The order of removal matters, and it changes the neighbours.
The trick: Pick which balloon in an interval bursts LAST; its neighbours are then fixed by the interval's edges.
-
Match a string against a pattern with '.' (any letter) and '*' (zero or more of the previous).
Show answer
Technique: 2-D DP / memoised recursion
The clue: Two strings matched with choices ('*' can mean zero or more).
The trick: At '*', either skip 'x*' entirely or use it once if the current letters match and stay on the pattern.
What to say in the interview
'Because our state depends on two varying constraints, I will build a 2D tabulation matrix to calculate the answers bottom-up.'
Follow-up prep
Can you optimize the space? (Hint: You usually only need to remember the *previous row*, not the entire matrix!)