Two-dimensional Dynamic Programming
One table, two inputs
The most reusable two-dimensional state in the course: how much of each input has been consumed.
Key idea
The state that unlocks the whole family
For problems comparing or combining two sequences, the state is a pair of positions: how much of the first has been consumed, and how much of the second.
So the answer at (i, j) is the answer to the problem restricted to the first i characters of one input and the first j of the other. That sentence covers a dozen well-known problems and is worth memorizing as a starting point.
The base row and column describe one input being empty, which is usually where the easy answers live.
Why it works
The transition splits on whether the ends match
Look at the last character of each consumed prefix. If they match, that pair can be used together and the problem reduces to (i-1, j-1) plus whatever using them is worth.
If they do not match, one of them must be given up, and you take the better of dropping the last character of the first input or of the second: (i-1, j) or (i, j-1).
Almost every problem in this family is that shape with a different notion of what using a matching pair is worth.
Below, two cells are filled from neighbors that are already known, one where the ends match and one where they do not.
Gotcha
The table is one bigger than the input
The table has one extra row and column so that index zero can mean nothing consumed. That is why a[i - 1] appears rather than a[i]: table index i refers to the first i characters, whose last one sits at input index i minus 1.
That off-by-one is the single most common bug in this family. Write down what the table index means before you write the loop, and check it against the base row: best[0][j] must be the answer when the first input is empty.
Tip
Contiguous is a different problem
The recurrence above allows the shared characters to be spread out. If they had to be adjacent in both inputs, it changes: a mismatch resets to zero rather than taking the better of two neighbors, and the answer is the maximum over the whole table rather than the corner.
Those two problems look almost identical and their recurrences differ in two places. Read the statement carefully for the word contiguous or substring versus subsequence, because the wrong reading produces a plausible answer.
Tip
Two rows are enough
Every cell reads the row above and the cell to its left, so keeping the previous row and the current one suffices, giving O(min of the two lengths) space if you make the shorter input the columns.
It can be reduced to a single row with one saved diagonal value, which is fiddly. Two rows is the version to write and it is enough for any follow-up about space.
Key idea
Recovering the answer, not just its size
The table holds sizes. To recover an actual shared sequence, walk backward from the corner: when the characters match, that character is part of the answer and you step diagonally; otherwise step toward whichever neighbor holds the larger value.
That reconstruction is a common follow-up and it needs the full table rather than two rows, which is a genuine trade worth naming when you propose the space optimization.
Cost
Cost
The table has one cell per pair of prefixes and each is constant work, so O(len(a) times len(b)) time and the same space, or O(min length) with rolling rows.
There is no substantially better general algorithm for this family, which is worth saying because it stops the conversation looking for one.
Fill part of the table
Build the shared-sequence table for a = "abc" and b = "ac". Table index i means the first i characters of a, and j means the first j of b. Fill in the row for i = 3, that is the whole of abc.
This activity type is not wired up yet.
Longest Common Subsequence
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.