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:

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:

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.

# A first implementation

```
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.

## Top-down dynamic programming

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.

## Bottom-up dynamic programming

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]
```

## What to use ?

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`

.

See a typo ? You can suggest a modification on Github.