Grokking Algorithms

Chapter 9
 
 
I
 
 
Dynamic programming
Remember, the values for the cells are usually what you’re trying to 
optimize. In this case, the values will probably be a number: the length 
of the longest substring that the two strings have in common.
How do you divide this problem into subproblems? You could compare 
substrings. Instead of comparing 
hish
and 
ish
, you could compare 
his
and
is
irst. Each cell will contain the length of the longest substring 
that two substrings have in common. his also gives you a clue that the 
axes will probably be the two words. So the grid probably looks like this.
If this seems like black magic to you, don’t worry. his is hard stuf—
that’s why I’m teaching it so late in the book! Later, I’ll give you an 
exercise so you can practice dynamic programming yourself.
Filling in the grid
Now you have a good idea of what the grid should look like. What’s the 
formula for illing in each cell of the grid? You can cheat a little, because 
you already know what the solution should be—
hish
and
ish
have a 
substring of length 3 in common:
ish
.
But that still doesn’t tell you the formula to use. Computer scientists 
sometimes joke about using the Feynman algorithm. he 
Feynman 
algorithm
is named ater the famous physicist Richard Feynman, and
it works like this: 
1. Write down the problem. 
2. hink real hard. 
3. Write down the solution.

---

181
Longest common substring
Computer scientists are a fun bunch!
he truth is, there’s no easy way to calculate the formula here. You 
have to experiment and try to ind something that works. Sometimes 
algorithms aren’t an exact recipe. hey’re a framework that you build 
your idea on top of.
Try to come up with a solution to this problem yourself. I’ll give you a 
hint—part of the grid looks like this.
What are the other values? Remember that each cell is the value of a 
subproblem.
Why does cell (3, 3) have a value of 2? Why does cell (3, 4) 
have a value of 0? 
Read on ater you’ve tried to come up with a formula yourself. Even if 
you don’t get it right, my explanation will make a lot more sense.

---

182