**acquire new users**and

**make more money**with their web businesses. I have

**ten years**of experience with

**SaaS projects**. If that’s something you need help with, we should get in touch!

These are my notes about a series of videos on dynamic programming. It showed me how to solve this kind of problems always in the same way.

Understanding this technique was useful:

- for AoC 2021 day 21 part2
- for AoC 2020 day 10

In this article, we are approaching different ways to solve the “Dice combination” problem from CSES.

Your task is to count the number of ways to construct

`sum n`

by throwing a dice one or more times. Each throw produce an outcome between 0 and 6.For example, if

`n = 3`

, there are 4 ways:

- 1+1+1
- 1+2
- 2+1
- 3

There are many ways to solve this problem. Lets give a try at a first implementation, then we’ll look at how to improve it.

```
def count_sum(n):
if n<0: return 0
if n==0: return 1
ans = 0
for i in range(1, 6+1):
ans += count_sum(n-i)
return ans
```

The problem with this recursive implementation right now: if we look at the call graph (that is to say: which function calls which ones), we will see a tree like this:

```
dp(10) will call:
├─dp(9) will call:
│ ├─dp(8)
│ ├─dp(7)
│ ├─…
│ ├─dp(3)
├─dp(8)
│ ├─dp(7)
│ ├─dp(6)
│ ├─…
├─dp(7)
│ …
├─dp(4)
```

Each function calls in turn many others, and we compute the same values over
and over again. We have an **exponential running time**. For high enough values of n, this implementation is not suitable anymore.

We can refactor our solution in order to **cache results**:

```
DP = {}
def count_sum_dp(n):
# have we reached a final state?
if n<0: return 0
if n==0: return 1
# did we store this result in cache already?
if n in DP:
return DP[n]
# if not, generate the value for this n
ans = 0
for i in range(1, 6+1):
ans += count_sum_dp(n-i)
# cache this result, and return it
DP[n] = ans
return ans
```

This was **top-down dynamic programming**: we start from n and go to 0. There is also **bottom up DP**: we start from 0, then move to n.

With bottom-up DP, we do not write a recursive function:

```
def count_sum_iter(n):
"""iterative, bottom up dynamic programming approach"""
ITER_DP = { i: -1 for i in range(n+1) }
# print(ITER_DP)
ITER_DP[0] = 1
# Now we need to fill our array:
# DP[x] = 0 for all x < 0
# DP[x] = DP[x-1] + DP[x-2] + ... + DP[x-6] for all x >=0
for i in range(1, n+1):
ans = 0
for dice in range(1, 6+1):
ans += ITER_DP[i-d] if i-d >=0 else 0
ITER_DP[i] = ans
return ITER_DP[n]
```

All 3 functions should answer the same thing.

```
assert(count_sum(3) == 4)
assert(count_sum_dp(3) == 4)
assert(count_sum_iter(3) == 4)
```

The difficulty with **bottom up DP** is that:

- it can be harder to reason about
- you have to fill the array in the right order. Here, we fill it from low to high, because we use the lower values first.

**Memoization** takes care of that automatically: we call our `dp`

function recursively, and if it’s already computed, the cached value is used, otherwise it’s computed recursively. The pattern is always the same and it’s a good idea to memorize it:

```
CACHE = {}
def some_dp_function(n):
if we have reached a final state:
return some value
if n in CACHE:
return CACHE[n]
# generate the final value for n using recursion:
ans = 0
for i in range(1, 6+1):
ans = f(some_dp_function(n-i))
CACHE[n] = ans
return ans
```

In Python, you can also use `cache`

or `lru_cache(max_size=None)`

from `functools`

.