2-D Dynamic Programming

2-D dynamic programming is the same discipline as 1-D — cache repeated subproblems instead of re-deriving them — with one extra dimension in the state. That extra dimension almost always comes from one of two places: a position in a grid (row, column), or a position in two strings at once (how far through the first, how far through the second). Recognizing which shape you're in tells you what the table's axes actually mean.

Grid DP: two ways in, one recurrence

Unique Paths is the cleanest version of grid DP: a robot moving only right or down means every cell has exactly two possible predecessors (above, or to the left), so dp[i][j] = dp[i-1][j] + dp[i][j-1] falls out immediately. Minimum Path Sum and Unique Paths II are the same recurrence with the combining operator swapped (min instead of +) or a hard constraint bolted on (an obstacle forces dp[i][j] = 0, which then naturally blocks anything trying to route through it). Maximal Square uses three predecessors instead of two — up, left, and diagonal — because extending a square by one row and one column needs all three neighboring squares to already support that larger size.

Two-string DP: match, skip, or both

Longest Common Subsequence is the foundational version: if the two current characters match, they must both belong to the answer (dp[i-1][j-1] + 1); if they don't, try dropping either character and keep the better result. Edit Distance generalizes this to three possible operations instead of "match or skip." Distinct Subsequences flips it from an optimization into a count — and the recurrence becomes an addition, not a max, because "don't use this character" and "use this character to match" are both always simultaneously valid contributions, not competing choices.

The one-line difference that changes the entire problem: LCS vs. Longest Common Substring

Longest Common Subsequence and Longest Common Substring have recurrences that look almost identical — until a mismatch. LCS carries the best answer forward (max(dp[i-1][j], dp[i][j-1])), because a subsequence is allowed to skip characters and keep going. A substring is contiguous, so a mismatch doesn't just fail to extend the run — it endsdp[i][j] resets to 0. Mixing these two rules up (using the LCS carry-forward for a substring problem, or the substring reset for a subsequence problem) produces a plausible-looking wrong answer, not a crash — which is exactly why stating what dp[i][j] means in plain English first catches this before it's written.

Interval DP: substrings of a single string

Longest Palindromic Substring and Palindromic Substrings both use a different axis pairing: dp[i][j] means "is s[i..j] a palindrome," over a single string. The fill order here is the detail most likely to trip you up: checking a length-L interval depends on the already-computed answer for the interval two characters shorter inside it, so the table must be filled by increasing interval length — not row-by-row or column-by-column, which is everyone's first instinct coming from grid DP.

When a choice doesn't commit: Interleaving String and Wildcard Matching

Interleaving String's *-free version and Wildcard Matching's * both share a shape: at some point, more than one action could be valid right now, and only checking every possibility (rather than greedily locking in one) guarantees finding a path that actually works out. Interleaving String's ambiguity is "which source contributes this next matching character" — a greedy preference for one source can walk into a dead end that backtracking would have avoided. Wildcard Matching's * is explicitly two possibilities at once (match zero more characters, or match one more and stay available) — encoded directly as an || in the recurrence rather than a single choice.

Common mistakes

• Confusing subsequence and substring recurrences — carrying the best-so-far forward on a mismatch (correct for LCS) versus resetting to 0 (correct for a contiguous match) are opposite rules for superficially similar problems.
• Filling an interval-DP table in the wrong order — row-by-row or column-by-column reads an entry (a shorter interior interval) that hasn't been computed yet; interval problems need increasing-length order specifically.
• Using max where the problem needs a sum (or vice versa) — Distinct Subsequences needs both "skip this character" and "use this character" counts added together, since both are always valid at once; treating them as competing alternatives (taking a max) undercounts.
• Committing to one branch too early — Interleaving String and Wildcard Matching both need every valid possibility considered at an ambiguous point, not just whichever one happens to match first.