2-D DP
Picture a spreadsheet where every formula only points at the cells above and to the left. Fill it from the top-left corner and each cell becomes a small finished answer. The bottom-right cell then holds the whole answer, built without redoing a single cell.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Longest Common Subsequence
or try
Two words of 1–6 lowercase letters, separated by a space.Make a table with a row of zeros on top and a column of zeros down the left.Step 1 of 18. “abcde” down the side, “ace” across the top. Zero row and column ready. Nothing filled yet.
Step 1 of 18
solution.ts▶ marks the line running now
function lcs(a: string, b: string): number {
const dp = Array.from({ length: a.length + 1 }, () =>
new Array(b.length + 1).fill(0));
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[a.length][b.length];
}
4 · Your turn
0 of 2 problems solved
- Medium01
Unique Paths
Warm-up: each cell adds the ways from above and left.
- Medium02
Longest Common Subsequence
The one you just watched. Write it from memory.