Dynamic Programming — Practice Set
In the style of 2ILC0 Algorithms (TU/e)
Four problems on dynamic-programming recurrences. Work through the questions first;
worked solutions begin on the last pages.
How these problems work. Each problem fixes a precise subproblem T [. . . ] (or S[. . . ]) defined
in words. You are asked to (i) compute specific entries of the table for a concrete input, (ii) give a
recursive formula for the table that can be turned into a polynomial-time dynamic program (covering
all base cases and guarding against out-of-bounds indices — you do not have to prove correctness or
give the algorithm), and, for the last problem, (iii) give pseudocode that reconstructs a solution from
the filled table. Whenever a subscript is 0 we interpret the prefix as the empty string/sequence.
1. Dynamic programming: Edit distance
In the Edit distance problem the input is two strings X = x1 , . . . , xn and Y = y1 , . . . , ym . We may
transform X into Y using three operations, each of cost 1: insert a single character, delete a single
character, or substitute one character by another. The cost of a transformation is the number of
operations used; the edit distance is the minimum possible cost of transforming X into Y .
For example, transforming sunday into saturday costs 3: insert a, insert t, and substitute n by r.
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ n and
0 ≤ j ≤ m, let T [i, j] be the edit distance between the length-i prefix Xi = x1 , . . . , xi and the
length-j prefix Yj = y1 , . . . , yj , i.e. the minimum number of operations needed to turn Xi into Yj .
(1a) [0.25 pt] For the input X = sunday, Y = saturday, what is the value of T [2, 4]?
(1b) [0.25 pt] For the same input, what is the value of T [5, 6]?
(1c) [1.0 pt] Give a recursive formula for the values of T [i, j] for all 0 ≤ i ≤ n and 0 ≤ j ≤ m,
and explain your formula briefly. Your formula should be such that one can use it for a dynamic-
programming algorithm that runs in polynomial time; you do not have to give the algorithm. Make
sure your recurrence covers all relevant cases.
2. Dynamic programming: Counting ways to make change
In the Coin change counting problem the input is a list of coin denominations c1 , . . . , ck (distinct
positive integers), of which we have an unlimited supply, together with a target amount A ≥ 0. We
want to count the number of ways to make exactly the amount A using these coins, where two ways
are considered the same if they use the same number of coins of each denomination (the order in
which coins are chosen does not matter).
1
, For example, with coins {1, 2, 5} there are 4 ways to make the amount 5, namely 5, 2+2+1, 2+1+1+1,
and 1+1+1+1+1.
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ k and
0 ≤ a ≤ A, let T [i, a] be the number of ways to make the amount a using only coins from the first i
denominations c1 , . . . , ci (again with unlimited supply of each).
(2a) [0.25 pt] For coins c = [1, 2, 5], what is the value of T [2, 4]?
(2b) [0.25 pt] For coins c = [1, 2, 5], what is the value of T [3, 6]?
(2c) [1.0 pt] Give a recursive formula for the values of T [i, a] for all 0 ≤ i ≤ k and 0 ≤ a ≤ A, and
explain your formula briefly. Your formula should be such that one can use it for a polynomial-time
dynamic-programming algorithm; you do not have to give the algorithm. Make sure your recurrence
covers all relevant cases.
3. Dynamic programming: Painting a row of houses
In the House painting problem there are n houses standing in a row, numbered 1, . . . , n, each of
which must be painted with exactly one of the three colours 1, 2, 3. Painting house i with colour c
costs a given non-negative integer Cost[i, c]. The only restriction is that two adjacent houses must
receive different colours. We want a colouring of all n houses, respecting the restriction, of minimum
total cost.
The cost table for our instance (n = 4) is:
colour 1 colour 2 colour 3
house 1 1 5 3
house 2 2 9 4
house 3 8 1 5
house 4 7 6 2
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ n and
each colour c ∈ {1, 2, 3}, let T [i, c] be the minimum total cost of painting the first i houses such that
adjacent houses among 1, . . . , i get different colours and house i is painted colour c. (For i = 0 there
are no houses to paint.)
(3a) [0.25 pt] For the table above, what is the value of T [3, 2]?
(3b) [0.25 pt] For the table above, what is the value of T [4, 1]?
2
In the style of 2ILC0 Algorithms (TU/e)
Four problems on dynamic-programming recurrences. Work through the questions first;
worked solutions begin on the last pages.
How these problems work. Each problem fixes a precise subproblem T [. . . ] (or S[. . . ]) defined
in words. You are asked to (i) compute specific entries of the table for a concrete input, (ii) give a
recursive formula for the table that can be turned into a polynomial-time dynamic program (covering
all base cases and guarding against out-of-bounds indices — you do not have to prove correctness or
give the algorithm), and, for the last problem, (iii) give pseudocode that reconstructs a solution from
the filled table. Whenever a subscript is 0 we interpret the prefix as the empty string/sequence.
1. Dynamic programming: Edit distance
In the Edit distance problem the input is two strings X = x1 , . . . , xn and Y = y1 , . . . , ym . We may
transform X into Y using three operations, each of cost 1: insert a single character, delete a single
character, or substitute one character by another. The cost of a transformation is the number of
operations used; the edit distance is the minimum possible cost of transforming X into Y .
For example, transforming sunday into saturday costs 3: insert a, insert t, and substitute n by r.
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ n and
0 ≤ j ≤ m, let T [i, j] be the edit distance between the length-i prefix Xi = x1 , . . . , xi and the
length-j prefix Yj = y1 , . . . , yj , i.e. the minimum number of operations needed to turn Xi into Yj .
(1a) [0.25 pt] For the input X = sunday, Y = saturday, what is the value of T [2, 4]?
(1b) [0.25 pt] For the same input, what is the value of T [5, 6]?
(1c) [1.0 pt] Give a recursive formula for the values of T [i, j] for all 0 ≤ i ≤ n and 0 ≤ j ≤ m,
and explain your formula briefly. Your formula should be such that one can use it for a dynamic-
programming algorithm that runs in polynomial time; you do not have to give the algorithm. Make
sure your recurrence covers all relevant cases.
2. Dynamic programming: Counting ways to make change
In the Coin change counting problem the input is a list of coin denominations c1 , . . . , ck (distinct
positive integers), of which we have an unlimited supply, together with a target amount A ≥ 0. We
want to count the number of ways to make exactly the amount A using these coins, where two ways
are considered the same if they use the same number of coins of each denomination (the order in
which coins are chosen does not matter).
1
, For example, with coins {1, 2, 5} there are 4 ways to make the amount 5, namely 5, 2+2+1, 2+1+1+1,
and 1+1+1+1+1.
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ k and
0 ≤ a ≤ A, let T [i, a] be the number of ways to make the amount a using only coins from the first i
denominations c1 , . . . , ci (again with unlimited supply of each).
(2a) [0.25 pt] For coins c = [1, 2, 5], what is the value of T [2, 4]?
(2b) [0.25 pt] For coins c = [1, 2, 5], what is the value of T [3, 6]?
(2c) [1.0 pt] Give a recursive formula for the values of T [i, a] for all 0 ≤ i ≤ k and 0 ≤ a ≤ A, and
explain your formula briefly. Your formula should be such that one can use it for a polynomial-time
dynamic-programming algorithm; you do not have to give the algorithm. Make sure your recurrence
covers all relevant cases.
3. Dynamic programming: Painting a row of houses
In the House painting problem there are n houses standing in a row, numbered 1, . . . , n, each of
which must be painted with exactly one of the three colours 1, 2, 3. Painting house i with colour c
costs a given non-negative integer Cost[i, c]. The only restriction is that two adjacent houses must
receive different colours. We want a colouring of all n houses, respecting the restriction, of minimum
total cost.
The cost table for our instance (n = 4) is:
colour 1 colour 2 colour 3
house 1 1 5 3
house 2 2 9 4
house 3 8 1 5
house 4 7 6 2
We solve this by dynamic programming with the following subproblem. For each 0 ≤ i ≤ n and
each colour c ∈ {1, 2, 3}, let T [i, c] be the minimum total cost of painting the first i houses such that
adjacent houses among 1, . . . , i get different colours and house i is painted colour c. (For i = 0 there
are no houses to paint.)
(3a) [0.25 pt] For the table above, what is the value of T [3, 2]?
(3b) [0.25 pt] For the table above, what is the value of T [4, 1]?
2
