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 nby 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:
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.