Dynamic Programming: Two Dimensions
Think of comparing two shopping lists to find the items they share, or figuring out the fewest edits to turn one sentence into another. Both need you to track a position in two things at once, not just one. The Dynamic Programming Basics lesson used a single moving index, dp[i]. Here the state grows to two dimensions: two strings, two positions in the same array, or one sequence plus an extra flag like "have I used my one free skip yet." This is where a lot of candidates' DP falls apart. Get comfortable with two-dimensional state and you've covered the pattern behind most "hard" DP interview questions.
2D DP state
When a problem compares or combines two sequences, or tracks one sequence plus something extra (like "how many items used so far" or "have I done X yet"), the state usually needs two indices: dp[i][j].
# Generic 2D DP table shape
dp = [[0] * (n + 1) for _ in range(m + 1)]The extra row and column, the +1 in each dimension, conventionally stands for the empty prefix: dp[0][j] and dp[i][0] are base cases meaning "zero characters or items considered from this side." This convention saves you from special-casing empty inputs everywhere inside the main loop.
How to recognize 2D DP: if comparing or combining two sequences means you need to know where you are in both of them, you need two indices. If it's really one sequence but you're also tracking an extra constraint, like a budget, a mode, or a used/unused flag, that constraint becomes the second dimension.
Remember: two strings, two positions. One string plus an extra fact you must remember, one position plus one flag. Either way, that's your second dimension.
String DP
String DP problems compare or transform two strings character by character. The state is dp[i][j] = "the answer considering the first i characters of string A and the first j characters of string B." The transition almost always branches on whether A[i-1] == B[j-1].
# Skeleton shared by LCS, Edit Distance, and most string-pair DP:
for i in range(1, m + 1):
for j in range(1, n + 1):
if A[i - 1] == B[j - 1]:
dp[i][j] = ... # characters match — extend some prior state
else:
dp[i][j] = ... # characters differ — combine other subproblemsSpace is often shrinkable from O(m×n) down to O(min(m,n)), because row i usually only depends on row i-1.
Remember: string DP is a grid where row
iand columnjmean "firsticharacters of A, firstjcharacters of B." The character comparison at that cell decides the transition.
State machines
Some DP problems, like stock trading or string parsing with modes, model the process as a finite state machine: dp[i][state] tracks the best value at step i while in a given state, and transitions move between states.
# Example shape: dp[i][0] = best value at step i in "state 0"
# dp[i][1] = best value at step i in "state 1"
# Buy/sell stock is the canonical example:
def maxProfit_stateMachine(prices: list[int]) -> int:
hold, not_hold = float('-inf'), 0 # state 0: holding a share, state 1: not
for price in prices:
hold, not_hold = max(hold, not_hold - price), max(not_hold, hold + price)
return not_holdThe key skill is drawing the state diagram first, on paper: what states exist, what moves between them are legal, what each move costs or earns, before writing any code. It's the same discipline as pinning down dp[i] correctly, just with an extra "which mode am I in" dimension.
Remember: draw the states and the arrows between them on paper before coding. Code the diagram, don't invent it in the loop.
Longest Common Subsequence
LeetCode 1143, DP, 2D
Intuition: A subsequence keeps the relative order of characters but can skip some. dp[i][j] = length of the longest common subsequence (LCS) of text1[:i] and text2[:j]. If the current characters match, they extend the LCS found without them; if not, take the better of skipping a character from either string.
Approach: dp[i][j] = dp[i-1][j-1] + 1 if text1[i-1] == text2[j-1], else max(dp[i-1][j], dp[i][j-1]).
def longestCommonSubsequence(text1: str, text2: str) -> int:
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]Worked example: "abcde" and "ace" share the subsequence "ace" (skip b and d), so the answer is 3.
Complexity: Time O(m·n), space O(m·n), shrinkable to O(min(m,n)) since row i only needs row i-1.
Common mistakes: confusing "subsequence" with "substring." LCS allows gaps, so dp[i][j] isn't restricted to characters at i-1, j-1 being part of one contiguous run. Also, off-by-one indexing between the 1-indexed dp table and 0-indexed strings: it's text1[i-1], not text1[i].
Remember: LCS skips freely; substring problems don't. Mixing those two up is the most common LCS bug.
Edit Distance
LeetCode 72, DP, 2D, Hard
Intuition: You want the fewest operations (insert, delete, replace) to turn word1 into word2. dp[i][j] = edit distance between word1[:i] and word2[:j]. If characters match, no operation is needed at this position; if not, take the best of the three possible operations plus 1.
Approach: dp[i][j] = dp[i-1][j-1] if characters match, else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (replace, delete, insert respectively).
def minDistance(word1: str, word2: str) -> int:
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 # delete all i characters of word1
for j in range(n + 1):
dp[0][j] = j # insert all j characters of word2
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 - 1], # replace
dp[i - 1][j], # delete from word1
dp[i][j - 1], # insert into word1
)
return dp[m][n]Complexity: Time O(m·n), space O(m·n), shrinkable to O(min(m,n)).
Common mistakes: forgetting the base-case row and column, dp[i][0] = i and dp[0][j] = j. Without these, comparing against an empty string gives wrong results. Also, mixing up which operation goes with which neighbor cell: delete is dp[i-1][j], insert is dp[i][j-1], replace is dp[i-1][j-1]. Draw a small table by hand once to lock this in.
Remember: three neighbors, three operations.
dp[i-1][j]deletes,dp[i][j-1]inserts,dp[i-1][j-1]replaces.
Longest Increasing Subsequence
LeetCode 300, DP, Binary search optimization
Intuition: dp[i] = length of the longest increasing subsequence ending exactly at index i. The O(n²) version checks every earlier smaller element. The O(n log n) version instead keeps an array tails, where tails[k] is the smallest possible tail value of an increasing subsequence of length k+1, updated with binary search.
Approach (O(n²), derive this one first): dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), defaulting to 1.
def lengthOfLIS_On2(nums: list[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Approach (O(n log n), the interview follow-up):
import bisect
def lengthOfLIS(nums: list[int]) -> int:
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Complexity: O(n²) DP: time O(n²), space O(n). Binary-search version: time O(n log n), space O(n).
Common mistakes: thinking tails is an actual LIS at the end. It isn't: it only tracks the smallest possible tail for each length, so its length equals the LIS length, but its contents aren't a real subsequence. Also, using bisect_right instead of bisect_left, which would wrongly allow non-strict increases for the "strictly increasing" version of this problem.
Remember:
tailsis a scoreboard of best-possible endings, not a real subsequence. Only its length matters for the answer.
Word Break
LeetCode 139, DP, String
Intuition: dp[i] = can s[:i] be split into dictionary words? dp[i] is true if some earlier split point j has dp[j] true and s[j:i] is itself a dictionary word.
Approach: dp[0] = True (an empty prefix is trivially splittable). For each i, check every j < i: if dp[j] and s[j:i] is in the word set, set dp[i] = True.
def wordBreak(s: str, wordDict: list[str]) -> bool:
word_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # no need to check other j once found
return dp[n]Complexity: Time O(n²) for the double loop, plus O(k) per substring slice and lookup where k is the average word length, so effectively O(n²·k) worst case; a set keeps membership checks O(1) on average. Space O(n) for dp, plus O(total dictionary characters) for word_set.
Common mistakes: treating this as needing to list every possible split, which is a different, more expensive problem (Word Break II); this variant only needs a yes/no answer. Also, forgetting the dp[0] = True base case, which anchors every later true value. Not breaking early once dp[i] is set is harmless for correctness but wastes time on large inputs.
Remember:
dp[i]asks one question: is there ANY earlier valid split pointjwhere the rest of the string is a dictionary word? One yes is enough.
Recovering the answer, not just its value
LCS and Edit Distance above both compute a number: a length or a cost. Getting the actual subsequence, or the actual sequence of edits, takes one more step: walk backward from dp[m][n], and at each cell figure out which transition produced it. In LCS, if text1[i-1] == text2[j-1], that character belongs to the answer and you step diagonally to dp[i-1][j-1]. Otherwise you step toward whichever neighbor, dp[i-1][j] or dp[i][j-1], matches the current cell's value. The same backward walk applied to the Edit Distance table recovers the actual sequence of inserts, deletes, and replacements. Interviewers often ask for this as a follow-up once the length-or-cost version works, so trace it through by hand once rather than meeting it cold in an interview.
Remember: the table gives you a number. Walking it backward, cell by cell, gives you the actual sequence of choices behind that number.