What this module covers: Module P-13's 2D DP compared one sequence against a resource constraint. This module covers 2D DP where the two dimensions are two separate sequences being compared against each other — the shape behind diff tools, spell-checkers, and fuzzy matching — plus a weighted variant of Module P-13's grid-path counting.
Given two strings, find the length of the longest subsequence common to both — not necessarily contiguous, just in the same relative order.
function longestCommonSubsequence(s1: string, s2: string): number { const m = s1.length, n = s2.length; // dp[i][j] = LCS length using the first i characters of s1 and first j characters of s2 const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s1[i - 1] === s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; // characters match — extend the subsequence found so far } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match — best of dropping a char from either side } } }
dp[i][j] = the LCS length considering only the first i characters of s1 and the first j characters of s2. On a match, extending the LCS found in the smaller subproblem (dp[i-1][j-1], both strings one character shorter) by one is clearly correct. On a mismatch, the current characters can't both be part of the LCS together, so the best answer must come from dropping one character from one side or the other — taking whichever of those two gives the longer result. Both dimensions here represent positions within separate sequences, unlike Module P-13's knapsack, where the second dimension was a resource budget.
Given one sequence, find the length of its longest strictly increasing subsequence (not necessarily contiguous).
function lengthOfLIS(nums: number[]): number { const n = nums.length; if (n === 0) return 0;
// dp[i] = length of the longest increasing subsequence that ENDS at index i const dp = new Array(n).fill(1); // every single element is trivially an increasing subsequence of length 1
for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); // extend the best subsequence ending at j, if nums[i] can follow it } } }
This version is O(n²) — for each position i, it checks every earlier position j. A key subtlety worth naming: dp[i] must specifically mean "the LIS ending exactly at index i," not "the LIS within the first i elements" — because a later element might need to extend a subsequence that ends partway through the array, not necessarily the overall best-so-far. The final answer is the maximum across the whole dp array, since the overall longest subsequence could end anywhere. (An O(n log n) version exists, maintaining a separate array of "smallest tail value for each achievable subsequence length" and using Module F-11's binary search to find where each new element belongs — a genuinely different technique layered on top of the same underlying problem, not covered in full here.)
The minimum number of single-character insertions, deletions, or substitutions needed to transform one string into another — the exact metric behind "did you mean...?" spell-check suggestions.
function editDistance(s1: string, s2: string): number { const m = s1.length, n = s2.length; // dp[i][j] = min edits to transform the first i characters of s1 into the first j characters of s2 const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i; // transforming to empty string: delete everything for (let j = 0; j <= n; j++) dp[0][j] = j; // transforming from empty string: insert everything
for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s1[i - 1] === s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; // characters already match — no edit needed here } else { dp[i][j] = 1 + Math.min( dp[i - 1][j], // delete a character from s1 dp[i][j - 1], // insert a character into s1 dp[i - 1][j - 1] // substitute a character in s1 ); } } }
return dp[m][n]; }
editDistance('horse', 'ros'); // 3
The base cases (dp[i][0] = i, dp[0][j] = j) capture the "transform to/from an empty string" edge case directly: turning i characters into nothing takes exactly i deletions, and building j characters from nothing takes exactly j insertions. On a mismatch, the three options inside Math.min correspond exactly to the three allowed edit operations, each one reducing the problem to a smaller, already-solved subproblem — delete (drop a character from s1, so i shrinks), insert (account for a character now placed in s1 to match s2, so j shrinks), or substitute (both shrink, since one character is swapped for another).
Module P-13's uniquePathscounted paths through a grid. A closely related problem costs them: given a grid where each cell has a cost, find the minimum total cost to travel from top-left to bottom-right, moving only right or down.
function minPathSum(grid: number[][]): number { const rows = grid.length, cols = grid[0].length; const dp: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(0));
dp[0][0] = grid[0][0]; for (let c = 1; c < cols; c++) dp[0][c] = dp[0][c - 1] + grid[0][c]; // only one way along the top row for (let r = 1; r < rows; r++) dp[r][0] = dp[r - 1][0] + grid[r][0]; // only one way down the left column
for (let r = 1; r < rows; r++) { for (let c = 1; c < cols; c++) { dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]); // cheapest of arriving from above or from the left } }
return dp[rows - 1][cols - 1]; }
Compare this directly to Module P-13's uniquePaths: the recurrence's shape is identical (dp[r][c] depends on dp[r-1][c] and dp[r][c-1]), but the combination rule changes from sum to min, because this problem asks "what's the cheapest way to arrive here" rather than "how many distinct ways are there to arrive here." Same state definition, same predecessor relationship, different question — and therefore a different combination rule, exactly the pattern flagged repeatedly across this DP sequence.
git diff and version control diff tools are built directly on longest common subsequence: the lines that appear unchanged between two file versions are exactly the LCS of the two files' line sequences — everything not part of that LCS is what gets shown as added or removed.
Spell-check and "did you mean" suggestions use edit distance directly: suggesting corrections within edit distance 1 or 2 of a misspelled word is precisely this module's editDistance function, run against a dictionary of candidate words.
Fuzzy search and autocomplete (search-as-you-type systems, deduplication of near-identical records) commonly use edit distance as a similarity metric to rank or filter candidates that aren't exact string matches but are "close enough."
Trend and streak analysis — the longest stretch of consistently increasing values in a metric time series (revenue, latency, user growth) — is a direct instance of longest increasing subsequence, applied to real, noisy data rather than an interview array.
Weighted route/resource-cost optimization — minimum-cost delivery routing on a grid-like map, or minimum-cost data-migration paths through a layered pipeline — is exactly minPathSum's shape, generalized beyond a literal grid to any DAG where cost accumulates along right/down-style edges.
LCS compares two separate sequences positionally, dp[i][j] = LCS length using the first i and j characters of each — extend on a match, take the best of dropping one character from either side on a mismatch.
LIS's dp[i] means "longest increasing subsequence ending exactly at i" — a subtlety that matters, since the overall answer requires checking the max across the whole table, not just the last entry.
Edit distance's three options (delete, insert, substitute) map directly onto three ways to shrink the 2D subproblem, with base cases handling the empty-string edge case explicitly.
Minimum Path Sum reuses Module P-13's exact grid-path recurrence shape, just swapping the combination rule from sum (counting paths) to min (finding cheapest cost) — the same state, a different question.
This entire module is powered by diff tools, spell-checkers, fuzzy search, and weighted routing in real production systems.
The next module, Greedy Algorithms: Local vs Global Optimum, moves away from dynamic programming's "consider every relevant subproblem" approach toward a faster, more fragile strategy: always take the locally best choice, and hope it adds up to the globally best one.
Knowledge Check
In longestCommonSubsequence, why does a character match at s1[i-1] === s2[j-1] lead to dp[i][j] = dp[i-1][j-1] + 1, specifically referencing the diagonal predecessor rather than dp[i-1][j] or dp[i][j-1]?
In lengthOfLIS, why must the final answer be computed as Math.max(...dp) across the entire array, rather than simply returning dp[n - 1] (the last computed entry)?
Comparing minPathSum to Module P-13's uniquePaths, what specifically changes between the two recurrences, and what does the module say this illustrates about dynamic programming problem-solving generally?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Written by Jatin Jain Saraf · Architect of SupraScan