4.5Classic DP: LCS, edit distance, LIS
The idea
LCS, edit distance and LIS are the classic sequence DPs: the table compares prefixes of the inputs.
Think of it like this: Comparing two documents prefix by prefix and recording how much they agree so far.
Why it exists
GATE asks for the final table value or the size of the table.
How it works
- LCS cell: if the letters match take the diagonal + 1, else the larger of up and left.
- Edit distance cell: min of delete, insert, replace/match.
- Both tables have (m + 1) × (n + 1) cells: O(mn).
- LIS: d[i] = 1 + max d[j] for j < i with a[j] < a[i], O(n²).
Worked example: LCS of AGGTAB and GXTXAYB
The table ends in 4: the common subsequence GTAB. Edit distance of kitten → sitting is 3.
Now play with it
- →Step through the LCS table and read the explanation for each cell.
- →Switch to edit distance for the same kind of table.
| G | X | T | X | A | Y | B | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | · | · | · | · | · | · | · |
| G | 0 | · | · | · | · | · | · | · |
| G | 0 | · | · | · | · | · | · | · |
| T | 0 | · | · | · | · | · | · | · |
| A | 0 | · | · | · | · | · | · | · |
| B | 0 | · | · | · | · | · | · | · |
- A ≠ G: c[1][1] = max(up 0, left 0) = 0
- A ≠ X: c[1][2] = max(up 0, left 0) = 0
- A ≠ T: c[1][3] = max(up 0, left 0) = 0
- A ≠ X: c[1][4] = max(up 0, left 0) = 0
- A = A: c[1][5] = c[0][4] + 1 = 1
- A ≠ Y: c[1][6] = max(up 0, left 1) = 1
- A ≠ B: c[1][7] = max(up 0, left 1) = 1
- G = G: c[2][1] = c[1][0] + 1 = 1
- G ≠ X: c[2][2] = max(up 0, left 1) = 1
- G ≠ T: c[2][3] = max(up 0, left 1) = 1
- G ≠ X: c[2][4] = max(up 0, left 1) = 1
- G ≠ A: c[2][5] = max(up 1, left 1) = 1
- G ≠ Y: c[2][6] = max(up 1, left 1) = 1
- G ≠ B: c[2][7] = max(up 1, left 1) = 1
- G = G: c[3][1] = c[2][0] + 1 = 1
- G ≠ X: c[3][2] = max(up 1, left 1) = 1
- G ≠ T: c[3][3] = max(up 1, left 1) = 1
- G ≠ X: c[3][4] = max(up 1, left 1) = 1
- G ≠ A: c[3][5] = max(up 1, left 1) = 1
- G ≠ Y: c[3][6] = max(up 1, left 1) = 1
- G ≠ B: c[3][7] = max(up 1, left 1) = 1
- T ≠ G: c[4][1] = max(up 1, left 0) = 1
- T ≠ X: c[4][2] = max(up 1, left 1) = 1
- T = T: c[4][3] = c[3][2] + 1 = 2
- T ≠ X: c[4][4] = max(up 1, left 2) = 2
- T ≠ A: c[4][5] = max(up 1, left 2) = 2
- T ≠ Y: c[4][6] = max(up 1, left 2) = 2
- T ≠ B: c[4][7] = max(up 1, left 2) = 2
- A ≠ G: c[5][1] = max(up 1, left 0) = 1
- A ≠ X: c[5][2] = max(up 1, left 1) = 1
- A ≠ T: c[5][3] = max(up 2, left 1) = 2
- A ≠ X: c[5][4] = max(up 2, left 2) = 2
- A = A: c[5][5] = c[4][4] + 1 = 3
- A ≠ Y: c[5][6] = max(up 2, left 3) = 3
- A ≠ B: c[5][7] = max(up 2, left 3) = 3
- B ≠ G: c[6][1] = max(up 1, left 0) = 1
- B ≠ X: c[6][2] = max(up 1, left 1) = 1
- B ≠ T: c[6][3] = max(up 2, left 1) = 2
- B ≠ X: c[6][4] = max(up 2, left 2) = 2
- B ≠ A: c[6][5] = max(up 3, left 2) = 3
- B ≠ Y: c[6][6] = max(up 3, left 3) = 3
- B = B: c[6][7] = c[5][6] + 1 = 4
Each cell depends only on cells already filled (up, left, diagonal; for the chain, shorter sub-chains), so the work is (number of cells) × (work per cell): O(mn) for LCS and edit distance, O(nW) for knapsack, O(n³) for the matrix chain.
| s | i | t | t | i | n | g | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| k | 1 | · | · | · | · | · | · | · |
| i | 2 | · | · | · | · | · | · | · |
| t | 3 | · | · | · | · | · | · | · |
| t | 4 | · | · | · | · | · | · | · |
| e | 5 | · | · | · | · | · | · | · |
| n | 6 | · | · | · | · | · | · | · |
- d[1][1] = min(delete 2, insert 2, replace 1) = 1
- d[1][2] = min(delete 3, insert 2, replace 2) = 2
- d[1][3] = min(delete 4, insert 3, replace 3) = 3
- d[1][4] = min(delete 5, insert 4, replace 4) = 4
- d[1][5] = min(delete 6, insert 5, replace 5) = 5
- d[1][6] = min(delete 7, insert 6, replace 6) = 6
- d[1][7] = min(delete 8, insert 7, replace 7) = 7
- d[2][1] = min(delete 2, insert 3, replace 2) = 2
- d[2][2] = min(delete 3, insert 3, match 1) = 1
- d[2][3] = min(delete 4, insert 2, replace 3) = 2
- d[2][4] = min(delete 5, insert 3, replace 4) = 3
- d[2][5] = min(delete 6, insert 4, match 4) = 4
- d[2][6] = min(delete 7, insert 5, replace 6) = 5
- d[2][7] = min(delete 8, insert 6, replace 7) = 6
- d[3][1] = min(delete 3, insert 4, replace 3) = 3
- d[3][2] = min(delete 2, insert 4, replace 3) = 2
- d[3][3] = min(delete 3, insert 3, match 1) = 1
- d[3][4] = min(delete 4, insert 2, match 2) = 2
- d[3][5] = min(delete 5, insert 3, replace 4) = 3
- d[3][6] = min(delete 6, insert 4, replace 5) = 4
- d[3][7] = min(delete 7, insert 5, replace 6) = 5
- d[4][1] = min(delete 4, insert 5, replace 4) = 4
- d[4][2] = min(delete 3, insert 5, replace 4) = 3
- d[4][3] = min(delete 2, insert 4, match 2) = 2
- d[4][4] = min(delete 3, insert 3, match 1) = 1
- d[4][5] = min(delete 4, insert 2, replace 3) = 2
- d[4][6] = min(delete 5, insert 3, replace 4) = 3
- d[4][7] = min(delete 6, insert 4, replace 5) = 4
- d[5][1] = min(delete 5, insert 6, replace 5) = 5
- d[5][2] = min(delete 4, insert 6, replace 5) = 4
- d[5][3] = min(delete 3, insert 5, replace 4) = 3
- d[5][4] = min(delete 2, insert 4, replace 3) = 2
- d[5][5] = min(delete 3, insert 3, replace 2) = 2
- d[5][6] = min(delete 4, insert 3, replace 3) = 3
- d[5][7] = min(delete 5, insert 4, replace 4) = 4
- d[6][1] = min(delete 6, insert 7, replace 6) = 6
- d[6][2] = min(delete 5, insert 7, replace 6) = 5
- d[6][3] = min(delete 4, insert 6, replace 5) = 4
- d[6][4] = min(delete 3, insert 5, replace 4) = 3
- d[6][5] = min(delete 3, insert 4, replace 3) = 3
- d[6][6] = min(delete 4, insert 4, match 2) = 2
- d[6][7] = min(delete 5, insert 3, replace 4) = 3
Each cell depends only on cells already filled (up, left, diagonal; for the chain, shorter sub-chains), so the work is (number of cells) × (work per cell): O(mn) for LCS and edit distance, O(nW) for knapsack, O(n³) for the matrix chain.
Check yourself
The time complexity of the standard DP for the LCS of strings of lengths m and n is
Exam notes (the dense version)
LCS of X (length m) and Y (length n): c[i][j] = c[i − 1][j − 1] + 1 if the symbols match, else max(c[i − 1][j], c[i][j − 1]); time and table size O(mn). Edit distance takes the min of insert, delete, replace. LIS is O(n²) with a simple DP or O(n log n) with binary search. Rod cutting, coin change and subset-sum follow the same pattern.
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.