KeiruaProd

I help my clients 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!
< Back to article list

Dynamic programming

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:

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.