# Examples of memoization

# Content of a Discrete Hyper Pyramid

We like to compute the number of possibilities $\P{n, N}$ for $x = (x_1, \ldots x_n)$ such that $x_i \in {0,1,\ldots, N}$ and $\sum_i x_i \leq N$. It is easy to see that $\P{n, N}$ satisfies the recursion:

with boundary conditions $\P{1, N} = N+1$ for all $N$. Note that by using the summation above, this condition can be replaced by $\P{0, N} = 1$ for all $N$.

Computing $\P{n,N}$ is easy when we use memoization. In fact, we can code the compuation in nearly one line!

```
from functools import lru_cache
@lru_cache(maxsize=128)
def P(n, N):
return (n==0) or sum( P(n-1, N-i) for i in range(N+1) )
```

Here is an example.

```
n=5
N=80
print(P(n = 5, N = 80))
```

```
32801517
```

# A probability problem

What is the probability $\P{n,k}$ to see at least $k$ heads in row when you throw a coin $n$ times? Suppose the coin lands on heads with probability $p$. We can see that $\P{n,k}$ must satisfy the recursion

because it is possible to throw $k$ times heads from the first throw, but otherwise you throw $i$, $i<k$, times a heads, then a tails, after which you have to start all over again.

Reasoning similarly, the expected number times $\E{n,k}$ to see at least $k$ heads in row when you throw a coin $n$ times must satisfy the recursion

```
p = 0.5
q = 1. - p
@lru_cache(maxsize=128)
def P(n, k):
"""
probability to see at least k heads in row when a coin is thrown n times
"""
if n < k:
return 0
else:
return sum(P(n-i,k) * p**(i-1) * q for i in range(1,k+1)) + p**k
@lru_cache(maxsize=128)
def E(n, k):
"""
expected number of times to see at least k heads in row when a coin is thrown n times
"""
if n < k:
return 0
else:
tot = sum(E(n-i,k) * p**(i-1) *q for i in range(1,k+1))
tot += p**k * (1 + E(n-k,k))
return tot
k = 2
for n in range(k,10):
print(n, P(n,k), E(n,k))
```

```
2 0.25 0.25
3 0.375 0.375
4 0.5 0.5625
5 0.59375 0.71875
6 0.671875 0.890625
7 0.734375 1.0546875
8 0.78515625 1.22265625
9 0.826171875 1.388671875
```