Dynamic programming · Data Structures and Algorithms

Why you need it

The intuition

Definition

Dynamic programming

Solving a problem by combining answers to overlapping subproblems, computing each subproblem once.

Memoisation

Caching a function's results by its arguments, so repeated calls return instantly.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

calls = 0

def ways(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(20), calls)

memo = {}
calls = 0

def ways_memo(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways_memo(n - 1) + ways_memo(n - 2)
    return memo[n]

print(ways_memo(20), calls)

1
2
3
4
5
6
7
8
9
10
11

def fewest_coins(coins, amount):
    INF = amount + 1
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(fewest_coins([1, 3, 4], 6))
print(fewest_coins([5, 10], 3))

Common mistakes

Quick quiz

1
2
3
4

ways = [1, 1]
for i in range(2, 6):
    ways.append(ways[i - 1] + ways[i - 2])
print(ways)

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

1. PredictFill the table

   Type exactly what this program prints.

2. ModifyMemoise it

   grid_paths(r, c) counts the paths from the top-left to the bottom-right of an r × c grid, moving only right or down. It's correct but exponential. Add a memo dict (or functools.lru_cache) so the speed test passes.

3. WriteFewest coins

   Write fewest_coins(coins, amount) that returns the fewest coins that add up to amount, or -1 if it can't be done. Build a table best from 0 up to amount.

Terms in this lesson