Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 19m 32s17 days 22 hours 19 minutes 32 seconds.

Algorithms - Dynamic Programming · 3:54

Grid and Two-Sequence DP

When the DP state has two indices, the table becomes a grid: a cell of a maze, or a prefix of each of two strings. We count right/down paths (35 on an open 4 x 5 grid, 7 once two walls go in), fill the longest common subsequence of TRADE and TREAD, and turn kitten into sitting with three edits by colouring every cell with the neighbour that won its minimum and walking back. Finally we cut the memory from a 400 MB table to two rows, measured on this Mac, and see why the edit script still needs the full table.

You will learn

Write grid-path DP (sum of the cells above and to the left, walls as 0) and relate the open-grid answer to a binomial coefficient
Write the LCS and edit-distance recurrences with 1-indexed tables over 0-indexed strings
Reconstruct an LCS or an edit script by walking back from the corner along winning neighbours
Reduce memory to two rows when only the value is needed, and know why the reconstruction needs the full table (or Hirschberg)

Chapters

PreviousLongest Increasing Subsequence NextGraph Representations