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.
Dostları ilə paylaş: