Dynamic Programming
2D Dynamic Programming
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
grid pathsedit distancelongest common subsequencematrixtwo strings
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Do two indexes define the state?
- Are you comparing two strings or walking a grid?
- Does each cell depend on nearby solved cells?
Classic problem
Longest Common Subsequence (LeetCode 1143) — return the length of the longest
subsequence present in both strings a and b.
Input: a = "abc", b = "abc"
Output: 3 — the full strings match, so the LCS is "abc", length 3.
Common pitfalls
Building the table with shared inner arrays.
Forgetting the extra row and column for empty prefixes.