Course notes for ESC190 Computer Algorithms and Data Structures
Dynamic programming refers to a class of problem solving techniques (another you have heard of is ‘divide and conquer’) which tries to break up a problem into subproblems and as these subproblems are solved, their values are used to construct the final solution as well as re-used to avoid unecessary computation. This is often a new way to solve problem to students so examples are very handy to understand DP. In later courses, you may revisit dynamic programming and specifically study what is called “the optimality” of a solution.
For now, let’s look at a first and familiar example:
We want to compute the n-th Fibonacci number, as defined by the recurence relation:
\[F_i = \begin{cases}0 & i=0\\1&i=1\\F_{i-1} + F_{i-2}&i>1\end{cases}\]Write a function that recursively computes the n-th Fibonacci (Python or C is fine).
While this works, it is extremely inefficient because it calculates the same values over and over again. This is because the function calls itself twice with the same argument in the recursive case. As a result, the time complexity of this implementation is exponential, which means it grows very quickly with increasing values of n.
Doing this computation by hand,or by using print statements, we can see that this implementation grows a call tree and its complexity can be found to be \(\mathcal O(1.61^n)\) - and it’s not a coincidence that the golden ratio shows up! So the naive recursive approach that would be suitable in ESC180 clearly grows exponentially.
This expensive computation motivates us to look for patterns and indeed:
\[F_3 = F_2 + F_1 = (F_1 + F_0) + F_1 = \dots = 2\]so it’s clear that we are repeating computations and this prompts us to store previous results and retrieve them later. This is called memoisation (which is not a typo, but you can think of “memorisation” as an analogy) and it’s accepted without further proof that we can store results in some hashtable such that lookup is done in constant time (i.e. without extra cost).
With memoisation, we can implement a more efficient algorithm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def fib(n, mem = {0: 0, 1: 1}):
if n in mem:
return mem[n]
# This section is commented out because
# mem is initialised with the base case
# values. This is called using a
# 'default parameter' and acts like a
# global variable since it lives in the
# stack..
#if n == 0:
# return 0
#if n == 1:
# return 1
mem[n] = fib(n-1, mem) + fib(n-2, mem)
return mem[n]
Therefore, if we have already computed something, we don’t have to go through an entire series of recursive calls! The time complexity of this implementation is now linear, because we only have to do \(3n\) recursive calls. Analysing the algorithm, we can see that each entry in mem is computed once exactly so fib(i-1) and fib(i-2) do not produce recursive calls. Since we compute up to \(n\) entries in mem, the time complexity is said to be linear, \(\mathcal O(n)\) (drop the constant 3). Note that this analysis assumes retrieval is constant and addition is constant in time, which is true for doubles, but may not be true for other data types (since fibonacci integers can increase exponentially)
In general, for dynamic programming:
fib_list to store solutions)Memoisation can be thought of as selectively populating an array of values from which we access solutions to subproblems in order to solve the original problem. Since recursion and iteration are equally expressive, we can equivalently rewrite the above algorithm to solve every subproblem up until the original problem is solved. Because there are at most n subproblems to solve (this is especially easy to see in the case of finding the n-th Fibonacci number), then it turns out that both memoisation and computing all subproblems run in linear time complexity \(\mathcal O(n)\) in the limit of n. We can think of this as a bottom up approach or as an iterative approach because we compute the solution to the smallest subproblem then store the result in an array of size n and move onto the next subproblem - that subproblem can now use prior results to speed up computation!
Let’s implement the solution to Fibonacci’s problem once more, using the iterative approach using a for-loop instead of a recursion.
Even though the two are equivalent, in practise there are some differences and in this case, the iterative implementation should truly make n computations.
As an aside not covered in the course: observe that in this particular case, we know that the current subproblem is always computed using the previous 2 so this removes the need for an if-statement which, at a really low level, is faster to execute by the processor since it doesn’t have to calculate branches ahead.
Open Ended Follow Up:
The size of this array is linear in n. Can you do this task in constant space (i.e. the size of the array does not depend on n)?
There are a row of \(n\) houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a
n x 3cost matrix. For example,costs[0][0]is the cost of painting house 0 with color red;costs[1][2]is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.
Note that the above wording was taken from a LeetCode medium problem, but encodes the same information as the problem in the lecture. (Generally, coding interviews will contain questions at this level, so it is good practice to do medium-level Leetcode problems fast if you are trying to get software engineering PEY positions at top companies.)
Let’s apply the Dynamic Programming Method:
Define a relationship between the subproblems and the original problem: \(\begin{cases}R(i) & = \text{cost}(i, \text{red}) + \text{min}(G(i-1),B(i-1)) \\G(i) & = \text{cost}(i, \text{green}) + \text{min}(R(i-1),B(i-1)) \\B(i) & = \text{cost}(i, \text{blue}) + \text{min}(R(i-1),G(i-1))\\ \text{Cost}(i) &= \text{min}(R(i), G(i), B(i)) \end{cases}\) Here, \(R(i), G(i), B(i)\) are the optimal cost if the \(i^{\text{th}}\) house was painted red, green, or blue respectively. Note that these equations also reflect that no two adjacent houses can be painted the same colour.
n x 3 cost matrix.Let’s see an implementation of the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# Suppose we have 6 houses
N = 6
# Cost matrix
houses = [[7, 6, 7, 8, 9, 20],
[3, 8, 9, 22, 12, 8],
[16, 10, 4, 2, 5, 7]]
cost = [[0] * N,
[0] * N,
[0] * N]
cost[0][0] = houses[0][0]
cost[1][0] = houses[1][0]
cost[2][0] = houses[2][0]
for i in range(1, N):
# the min cost to paint the first i houses, with the i-th being painted red
cost[0][i] = houses[0][i] + min(cost[1][i-1], cost[2][i-1])
# the min cost to paint the first i houses, with the i-th being painted green
cost[1][i] = houses[1][i] + min(cost[0][i-1], cost[2][i-1])
# the min cost to paint the first i houses, with the i-th being painted blue
cost[2][i] = houses[2][i] + min(cost[0][i-1], cost[1][i-1])
min(cost[0][5], cost[1][5], cost[2][5])
cols = [0] * N
i = N-1
if cost[0][N-1] <= min(cost[1][N-1], cost[2][N-1]):
cols[N-1] = 0
elif cost[1][N-1] <= min(cost[0][N-1], cost[2][N-1]):
cols[N-1] = 1
else:
cols[N-1] = 2
for i in range(N-2, -1, -1):
cur_min = 10000
cur_min_col = -1
for col in [0, 1, 2]:
if col == cols[i+1]:
continue
if cost[col][i] < cur_min:
cur_min = cost[col][i]
cur_min_col = col
cols[i] = cur_min_col
def paint_house_cost(houses, col, i):
'''Return the cost of painting houses
0, 1, 2, ,,, i, with the i-th houses painted col
and the total cost minimized'''
if i == 0:
return houses[col][i]
cur_min = sum(sum(costs) for costs in houses)
cur_min_col = -1
for color in [0, 1, 2]:
if color == col:
continue
cost_color_i = paint_house_cost(houses, color, i-1)
if cost_color_i < cur_min:
cur_min = cost_color_i
cur_min_col = color
return houses[col][i] + cur_min
Given a list of n denominations of coins \(\{d_1, d_2, \dots, d_n\}\) and a target sum \(V\), find the minimum number of coins needed to make change for the target sum.
Using Canadian coins, this problem turns out to be quite straightforwards since the denominations (\(\{5, 10, 25, 100, 200\}\)) are set up such that a greedy approach where picking the highest value coin possible every time works out to produce the smallest number of coins picked (e.g. 75¢ is always minimally made with 3 25¢ coins).
What about the penny?? You may have keenly noticed that the 1¢ denomination is missing from the Canadian coins list. As a fun aside, show that the solution is off by at most 4 coins when missing the penny then, show that rounding the original target value to the nearest 5¢ increment bounds the error to at most 2 coins.
A better example would be a list of 3 denominations \(\{1, 4, 5\}\) with a target sum of 8$. We can easily see that the answer is 2 coins of 4$ - note that the greedy approach does not work in this case because the list of denominations contains coprime pairs.
Let’s define \(\text{OPT}(v) := \text{minimum of coins to make } v\) as the solution to a problem with target sum \(v\) with base case of \(\text{OPT}(0) = 0\). Note that we cannot make a negative sum so for posterity we impose \(\text{OPT}(v < 0) = \infty\). Now, let’s apply the Dynamic Programming Method:
To implement the iterative (bottom-up) solution in Python, we set up an array where each index corresponds to a target amount:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import numpy as np
def make_change(denom, target):
OPT = np.inf * np.ones(target + 1)
OPT[0] = 0
for amount in range(1, target + 1):
# check all denominations
for d in denom:
# can we use this denomination?
if amount - d >= 0:
# is this the best way to make this amount?
if OPT[amount - d] + 1 < OPT[amount]:
# update the optimal solution
OPT[amount] = OPT[amount - d] + 1
return OPT[target]
We initialize all entries to np.inf (meaning it’s impossible to make that amount), except OPT[0] = 0. We then use a bottom-up approach: to compute OPT(target) we need OPT(target - 1), which needs OPT(target - 2), and so on all the way to OPT(1). By iterating upward from 1, every subproblem we depend on is already solved when we need it.
For each amount, we loop over all denominations d. If amount - d >= 0, then we could use coin d, leaving amount - d left to make — which costs OPT[amount - d] coins optimally. So the total cost of choosing denomination d is OPT[amount - d] + 1. We keep the minimum across all such choices.
For our example (denom = [1, 4, 5], target = 8), the array evolves as follows:
1
2
3
4
5
6
7
OPT = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] # initial
OPT = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞] # amount=1: use coin 1
OPT = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞] # amount=2: use coin 1 twice
OPT = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞] # amount=3: use coin 1 thrice
OPT = [0, 1, 2, 3, 1, ∞, ∞, ∞, ∞] # amount=4: use coin 4
OPT = [0, 1, 2, 3, 1, 1, ∞, ∞, ∞] # amount=5: use coin 5
OPT = [0, 1, 2, 3, 1, 1, 2, 2, 2] # ... continuing to target=8
So OPT[8] = 2, corresponding to using two coins of value 4.
The time complexity of this solution is \(\mathcal{O}(d \cdot t)\) where \(d\) is the number of denominations and \(t\) is the target amount, since for each of the \(t\) amounts we loop over all \(d\) denominations. The space complexity is \(\mathcal{O}(t)\) for the OPT array.
Knowing the optimal number of coins isn’t always enough — we also want to know which coins to use. To do this, we maintain a second structure OPT_soln that tracks the actual coins used for the optimal solution at each amount. Every time we update OPT[amount], we also update OPT_soln[amount]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np
def make_change(denom, target):
OPT = np.inf * np.ones(target + 1)
OPT[0] = 0
OPT_soln = {}
OPT_soln[0] = []
for amount in range(1, target + 1):
for d in denom:
if amount - d >= 0:
if OPT[amount - d] + 1 < OPT[amount]:
OPT[amount] = OPT[amount - d] + 1
OPT_soln[amount] = OPT_soln[amount - d] + [d]
return OPT_soln.get(target, None)
OPT_soln[amount] gets overwritten every time we find a better (fewer-coins) solution, so it always reflects the optimal combination. The get(target, None) handles the case where it’s impossible to make the target amount (e.g. if the denomination 1 is absent and the target is not reachable).
Running this on our example gives:
1
2
3
4
5
6
7
8
9
{0: [],
1: [1],
2: [1, 1],
3: [1, 1, 1],
4: [4],
5: [5],
6: [5, 1],
7: [5, 1, 1],
8: [4, 4]}
We can also write a recursive solution. Structurally it’s very similar to the iterative one — we’ve just swapped square brackets for round brackets (array indexing for function calls):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np
def make_change_recursive(denom, target):
if target == 0:
return 0
if target < 0:
return np.inf
min_coins = np.inf
for d in denom:
cur_min = make_change_recursive(denom, target - d) + 1
if cur_min < min_coins:
min_coins = cur_min
return min_coins
However, this is extremely inefficient. With 3 denominations, to compute OPT(t) we make 3 recursive calls, each of which makes 3 more, and so on. The total number of calls is bounded by \(3^0 + 3^1 + \cdots + 3^t = \mathcal{O}(3^t)\). In general, the time complexity without memoisation is \(\mathcal{O}(d^t)\) where \(d\) is the number of denominations.
As with Fibonacci, we can fix the exponential blowup by caching previously computed results:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import numpy as np
def make_change_recursive(denom, target, memo={}, solns={}):
if target in memo:
return memo[target], solns[target]
if target == 0:
memo[0] = 0
solns[0] = []
return 0, []
if target < 0:
memo[target] = np.inf
solns[target] = None
return np.inf, None
min_coins = np.inf
optimal_soln = None
for d in denom:
cur_min, cur_soln = make_change_recursive(denom, target - d, memo, solns)
if cur_min < min_coins:
min_coins = cur_min + 1
optimal_soln = cur_soln + [d]
memo[target] = min_coins
solns[target] = optimal_soln
return min_coins, optimal_soln
With memoisation, each distinct target value is computed exactly once. Since there are at most \(t + 1\) distinct targets and for each we loop over \(d\) denominations, the time complexity drops to \(\mathcal{O}(d \cdot t)\) — the same as the iterative solution.
Memoisation vs. Iterative: In many cases, both approaches yield the same time complexity. However, memoisation (top-down) can be slightly more efficient in practice if many subproblems are never needed — we only recurse into values we actually encounter. The iterative (bottom-up) approach always computes every subproblem from 0 to \(t\), even if most are unnecessary. For sparse denominations with a large target, this difference can matter.
This problem is taken from lab 8 (also from the 2024 Exam)
Given a non-empty string \(s\) and a dictionary \(\text{wordDict}\) containing a list of non-empty words, determin if \(s\) can be segmented into a space-separated sequence of one or more dictionary words.
clarifying: \(\text{wordDict}\) is a Python
list.For example: Given \(s=\) “applepenapple” and \(\text{wordDict}=\) [“apple”, “pen”]
Return
Truebecause we can segment the string into “apple pen apple”
Observe that this problem is very similar to the coin change problem in that we can fit each word in the dictionary as a prefix to the string and solve a smaller problem so the analogy is that the wordDict is a list of denominations that potentially make up the string.
Let’s work out the above example: If we are specifically interested in knowing if the string can be seegmented (later we will try to retrieve the segmentation) then we can try:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
s = "applepenapple"
wordDict = ["apple", "pen", "app"] # I'm adding "app" to make the example non-trivial
canSegment(s, wordDict) = canSegment("penapple", wordDict) OR
canSegment("lepenapple", wordDict)
# Solve first subproblem
canSegment("lepenapple", wordDict) = False # There are no words that fit as a prefix
# Solve second subproblem
canSegment("penapple", wordDict) = canSegment("apple", wordDict)
# Solve third subproblem
canSegment("apple", wordDict) = True # "apple" is a dictionary word!
# Bubble up the solutions
canSegment(s, wordDict) = ( (True) ) OR (False)
= True
Let’s apply DP more formally:
True if the substring \(s[0:i]\) can be segmented using wordDict. Then
\(s[0:i]\) is segmentable if there is some word \(w\) in the dictionary such that \(s\) ends with \(w\) at position \(i\), and the prefix before that ending is also segmentable.dp of size \(n+1\) where \(n\) is the length of the string \(s\).dp[n].1
2
3
4
5
6
7
8
9
10
11
12
13
def canSegment(s, wordDict):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty string is trivially segmentable
for i in range(1, n + 1):
for w in wordDict:
# does word w end exactly at position i?
if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
dp[i] = True
break # no need to check further words
return dp[n]
dp[0] = True is our base case: the empty prefix can always be “segmented” (with zero words). For each position \(i\) from 1 to \(n\), we check every word \(w\) in the dictionary. If the substring ending at \(i\) matches \(w\) and the prefix before it (dp[i - len(w)]) is already segmentable, then dp[i] = True.
Running through our example with s = "applepenapple" and wordDict = ["apple", "pen", "app"]:
1
2
3
4
dp[0] = True # ""
dp[5] = True # "apple"
dp[8] = True # "apple" + "pen"
dp[13] = True # "apple" + "pen" + "apple"
So dp[13] = True and we return True.
Just as in the coin change problem, we may want to retrieve the actual segmentation, not just whether one exists. We maintain a second array dp_soln where dp_soln[i] stores a segmentation of s[0:i]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canSegmentAndRetrieve(s, wordDict):
n = len(s)
dp = [False] * (n + 1)
dp_soln = [None] * (n + 1)
dp[0] = True
dp_soln[0] = []
for i in range(1, n + 1):
for w in wordDict:
if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
dp[i] = True
dp_soln[i] = dp_soln[i - len(w)] + [w]
break
return dp_soln[n] if dp[n] else None
For our example, this returns ["apple", "pen", "apple"].
For completeness, we can also write the recursive solution with memoisation. We work top-down from the full string, trying every word as a potential first word:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def canSegment(s, wordDict, memo={}):
if s in memo:
return memo[s]
if s == "":
return True
for w in wordDict:
if s.startswith(w):
if canSegment(s[len(w):], wordDict, memo):
memo[s] = True
return True
memo[s] = False
return False