Source code online books for professionals by professionals

Figure 8-1.  Recursion trees showing the impact of memoization. Node labels are subproblem parameters
7
This is still just an example for illustrating the basic principles.
8
For example, this “In or not?” approach is used in solving the knapsack problem, later in this chapter.

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
168
Another way of interpreting the pattern (as hinted at by the figure) is path counting. How many paths are there, 
if you go only downward, past the dotted lines, from the top cell to each of the others? This leads us to the same 
recurrence—we can come either from the cell above to the left or from the one above to the right. The number of 
paths is therefore the sum of the two. This means that the numbers are proportional to the probability of passing each 
of them if you make each left/right choice randomly on your way down. This is exactly what happens in games like the 
Japanese game Pachinko or in Plinko on The Price Is Right. There, a ball is dropped at the top and falls down between 
pins placed in some regular grid (such as the intersections of the hexagonal grid in Figure 
8-2
). I’ll get back to this path 
counting in the next section—it’s actually more important than it might seem at the moment.
The code for C(n,k) is trivial:
 
>>> @memo
>>> def C(n,k):
...     if k == 0: return 1
...     if n == 0: return 0
...     return C(n-1,k-1) + C(n-1,k)
>>> C(4,2)
6
>>> C(10,7)
120
>>> C(100,50)
100891344545564193334812497256
 
You should try it both with and without the @memo, though, to convince yourself of the enormous difference 
between the two versions. Usually, we associate caching with some constant-factor speedup, but this is another 
ballpark entirely. For most of the problems we’ll consider, the memoization will mean the difference between 
exponential and polynomial running time.