Grokking Algorithms

Longest common subsequence—solution
Here’s the final grid.

---

185
Longest common substring
Here’s my formula for filling in each cell.
And here it is in pseudocode:
if word_a[i] == word_b[j]: 
The letters match.
cell[i][j] = cell[i-1][j-1] + 1
else: 
The letters don’t match.
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
Whew—you did it! This is definitely one of the toughest chapters in the 
book. So is dynamic programming ever really used?
 Yes:
• Biologists use the longest common subsequence to find similarities 
in DNA strands. They can use this to tell how similar two animals or 
two diseases are. The longest common subsequence is being used to 
find a cure for multiple sclerosis.
• Have you ever used diff (like 
git diff
)? Diff tells you the differences 
between two files, and it uses dynamic programming to do so.
• We talked about string similarity. 
Levenshtein distance
measures 
how similar two strings are, and it uses dynamic programming. 
Levenshtein distance is used for everything from spell-check to 
figuring out whether a user is uploading copyrighted data. 

---

186
Chapter 9
 
 
I
 
 
Dynamic programming
• Have you ever used an app that does word wrap, like Microsoft Word? 
How does it figure out where to wrap so that the line length stays 
consistent? Dynamic programming!
EXERCISE
9.3
Draw and fill in the grid to calculate the longest common substring 
between 
blue 
and 
clues
.
Recap
• Dynamic programming is useful when you’re trying to optimize 
something given a constraint. 
• You can use dynamic programming when the problem can be
broken into discrete subproblems.
• Every dynamic-programming solution involves a grid.
• The values in the cells are usually what you’re trying to optimize.
• Each cell is a subproblem, so think about how you can divide your 
problem into subproblems.
• There’s no single formula for calculating a dynamic-programming 
solution.

---

187
In this chapter
• You learn to build a classification system using
the k-nearest neighbors algorithm.
• You learn about feature extraction.
• You learn about regression: predicting a number, 
like the value of a stock tomorrow, or how much
a user will enjoy a movie.
• You learn about the use cases and limitations
of k-nearest neighbors.