0
Challenge · 67Dynamic Programming
Subsequence DP: LIS and LCS
DPused in ~75% of apps
Subsequences are not substrings. You may skip, but you may not reorder, and that one rule produces the last big family of DP questions. One moving index gives a one dimensional table, two moving indexes give two dimensions, and that is the whole classification.
Core idea. For one sequence, each position asks what the best answer ending here is, which means looking back at every earlier position it could extend. For two sequences, the state is a position in each, and at every pair you either match both characters or skip one of them.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
filling the grid, one cell at a time
the costs
1
3
1
1
5
1
4
2
1
best cost to reach each cell
1
the corner has no choice, so it is just its own cost
step 1 of 10
Each cell reads only the one above and the one to the left, which is why filling row by row always finds them ready.
↑ play a little first, then dig in