Last week we saw how to write a recursive function that prints out all the ways to form a sum with Czech coins. We assumed that order matters, e.g. 1 + 2 and 2 + 1 are distinct sums. Here was our program's output for N = 5:
1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 1 + 2 + 2 2 + 1 + 1 + 1 2 + 1 + 2 2 + 2 + 1 5
Now suppose that order does not matter - for example, 1 + 2 and 2 + 1 are considered to be the same sum, so we only want to print one of these. How can we achieve this? In theory we could use the previous function to generate all possible sums, then somehow filter out duplicates, but that would be extremely inefficient since each sum can be permuted in many possible ways. Instead, let's modify our code so that it only considers sums in which integers appear in non-increasing order. For example, if N = 10 then it will print 5 + 2 + 2 + 1, but not any other permutation of these numbers.
We can accomplish this by making a small change to
our recursive helper function: it will take an extra argument max
indicating the maximum value of any coin which may be chosen at any
future point on the current branch of the decision tree. For example,
after we have chosen the coins 5 and 2, we will pass max
= 2 so that any coin chosen after that cannot be more than 2. That
will force each solution to be non-increasing. Here is the modified
code:
int[] coins = { 1, 2, 5, 10, 20, 50 };
void sum(int n) {
Stack<int> nums = [];
// Only use coins of size <= max.
void go(int rem, int max) {
if (rem == 0)
print(string.Join(" + ", nums.Reverse()));
else
foreach (int c in coins)
if (c <= rem && c <= max) {
nums.Push(c);
go(rem - c, c);
nums.Pop();
}
}
go(n, n);
}
The call sum2(5) will produce this output:
1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 5
We can solve a large number of problems using an exhaustive search. This means that we search through a problem space, looking for solutions - typically those which satisfy various constraints.
Typically our search will be recursive, so it will explore a tree of possibilities. However the shape of this tree may be different than in the combinatorial problems we saw above, because some parts of the tree will be cut off. That's because as we explore the tree, at some points there may be no decision we can make that will satisfy the problem's constraints. So at that point the search will backtrack and explore the next possibility. This approach is sometimes called a backtracking depth-first search.
A classic example of a problem that we can solve in this way is the N queens puzzle. Our goal is to place N queens on a chessboard such that none of them attack any other. Recall that queens in chess may move horizontally, vertically, or diagonally.
A moment's reflection will show that the puzzle has a trivial solution for N = 1, and no possible solutions for N = 2 or N = 3. Now let's think about how to search for a solution for N = 4.
Certainly we may only place one queen in any row. And, since we must place N queens, every row will need to contain a queen. So in this problem the first decision we may make is where to place the queen in the first row. After that, we can decide where to place the queen in the second row, and so on. As we explore this tree of possibilities, we will not consider all possible ways to place N queens in N rows (there are NN of those) since the search will only explore parts of the tree where all queens placed so far satisfy the constraints, i.e. don't attack each other.
Here is a partial search tree for N = 4:
In the leftmost two branches of this tree, the search gets cut off because there is no valid position in which to place a queen in the next row. The third branch leads to a solution. If we allow our search to continue past that point, it will find one more solution (which is a rotated version of this one).
One easy way to write this search in
C# is to use a stack that holds the positions of all the queens
placed so far. We'll define a type Pos that holds an (x,
y) pair which is the position of a single queen. Here is our
solution:
using static System.Console;
using static System.Math;
using Pos = (int x, int y);
// Return true if queens at the given positions attack each other.
bool attack(Pos p, Pos q) =>
p.x == q.x || p.y == q.y || Abs(p.x - q.x) == Abs(p.y - q.y);
void print_board(int n, Stack<Pos> queens) {
for (int y = 0 ; y < n ; ++y) {
for (int x = 0 ; x < n ; ++x)
Write(queens.Contains((x, y)) ? "Q " : ". ");
WriteLine();
}
WriteLine();
}
void queens(int n) {
Stack<Pos> queens = [];
void go(int y) {
if (y == n) {
print_board(n, queens);
return;
}
for (int x = 0; x < n ; ++x)
if (!queens.Any(q => attack((x, y), q))) {
queens.Push((x, y));
go(y + 1);
queens.Pop();
}
}
go(0);
}Let's run this function to find a solution for N = 12. The call
queens(12);
produces this output as the first solution it finds:
Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . Q . . . . . . . .
Dynamic programming is a general technique that we can use to solve a wide variety of problems. Many of these problems involve optimization, i.e. finding the shortest/longest/best solution to a certain problem.
Problems solvable using dynamic programming generally have the following characteristics:
They have a recursive structure. In other words, the problem's solution can be expressed recursively as a function of the solutions to one or more subproblems. A subproblem is a smaller instance of the same problem.
They have overlapping subproblems. A direct recursive implemention solves the same subproblems over and over again, leading to exponential inefficiency.
Usually we can dramatically improve the running time by arranging so that each subproblem will be solved only once. There are two ways to do that:
In a top-down implementation, we keep the same recursive code structure but add a cache of solved subproblems. This technique is called memoization.
In a bottom-up implementation, we also use a data structure (typically an array) to hold subproblem solutions, but we build up these solutions iteratively.
Generally we prefer a bottom-up solution, because
A bottom-up implementation is generally more efficient.
The running time of the bottom-up implementation is usually more obvious.
We will first study one-dimensional dynamic programming problems, which have a straightforward recursive structure. Next week, we will look at two-dimensional problems, which are a bit more complex.
Computing the Fibonacci number Fn is a trivial example of dynamic programming. Recall that the Fibonacci numbers are defined as
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 (n ≥ 3)
yielding the sequence 1, 1, 2, 3, 5, 8, 13, 21, …
Here is a recursive function that naively computes the n-th Fibonacci number:
int fib(int n) =>
n < 3 ? 1 : fib(n - 1) + fib(n – 2);What is its running time? The running time T(n) obeys the recurrence
T(n) = T(n – 1) + T(n – 2)
This is the recurrence that defines the Fibonacci numbers themselves! In other words,
T(n) = O(Fn)
The Fibonacci numbers themselves increase exponentially. It can be shown mathematically that
Fn = O(φn)
where
φ = (1 + √5) / 2
So fib runs in exponential time! That
may come as a surprise, since the function looks so direct and
simple. Fundamentally it is inefficient because it is solving the
same subproblems repeatedly. For example, fib(10) will
compute fib(9)
+ fib(8). The recursive call to fib(9) will
compute fib(8) + fib(7), and so we see that
we already have two independent calls to fib(8). Each of
those calls in turn will solve smaller subproblems over and over
again. In a problem with a recursive structure such as this one, the
repeated work multiplies exponentially, so that the smallest
subproblems (e.g. fib(3)) are computed an enormous
number of times.
As mentioned above, one way we can eliminate the
repeated work is to use a cache that stores answers to subproblems we
have already solved. This technique is called memoization.
Here is a memoized implementation of fib, using a local
function:
int fib(int n) {
int[] cache = new int[n + 1];
cache[1] = 1;
cache[2] = 1;
int f(int i) {
if (cache[i] == 0)
cache[i] = f(i - 1) + f(i - 2);
return cache[i];
}
return f(n);
}
Above, the cache array holds all the Fibonacci numbers
we have already computed. In other words, if we have already computed
Fi, then cache[i]
= Fi.
Otherwise, cache[i]
= 0.
This memoized version runs in linear time, because the line
cache[i] = f(n - 1) + f(n - 2);
runs only once for each value of i. This is a dramatic improvement!
In this particular recursive problem, the subproblem structure is quite straightforward: each Fibonacci number Fn depends only on the two Fibonacci numbers below it, i.e. Fn-1 and Fn-2. Thus, to compute all the Fibonacci numbers up to Fn we may simply start at the bottom, i.e. the values F1 and F2, and work our way upward, first computing F3 using F1 and F2, then F4 and so on. Here is the implementation:
int fib(int n) {
int[] a = new int[n + 1];
a[1] = a[2] = 1;
for (int k = 3 ; k <= n ; ++n)
a[k] = a[k - 1] + a[k - 2];
return a[n];
}Clearly this will also run in linear time. Note that this implementation is not even a recursive function. This is typical: a bottom-up solution consists of one or more loops, without recursion.
This example may seem trivial. But the key idea is that we can efficiently solve a recursive problem by solving subproblem instances in a bottom-up fashion, and as we will see we can apply this idea to many other problems.
The rod cutting problem is a classic dynamic programming problem. Suppose that we have a rod that is n cm long. We may cut it into any number of pieces that we like, but each piece's length must be an integer. We will sell all the pieces, and we have a table of prices that tells us how much we will receive for a piece of any given length. The problem is to determine how to cut the rod so as to maximize our profit.
We can express an optimal solution recursively. Let Pi be the given price for selling a piece of size i. We want to compute Vn, which is the maximum profit that we can attain by chopping a rod of length n into pieces and selling them. Any partition of the rod will begin with a piece of size i cm for some value 1 ≤ i ≤ n. Selling that piece will yield a profit of Pi. The maximum profit for dividing and selling the rest of the rod will be Vn – i. So Vn, i.e. the maximum profit for all possible partitions, will equal the maximum value for 1 ≤ i ≤ n of
Pi + Vn – i
Here is a naive recursive solution to the problem:
// Table of prices for different piece sizes.
int[] prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
// Return the largest possible profit for cutting a rod of length n,
// given a table with the prices for pieces from lengths 1 .. n.
int profit(int n) {
int best = 0;
for (int i = 1 ; i <= n ; ++i)
best = Max(best, prices[i] + profit(n - i));
return best;
}
This solution runs in exponential time,
because for each possible size k it will recompute profit(k)
many times.
This solution uses bottom-up dynamic programming:
// Return the largest possible profit for cutting a rod of length n,
// given a table with the prices for pieces from lengths 1 .. n.
int profit(int n) {
int[] best = new int[n + 1]; // best possible price for each size
for (int k = 1 ; k <= n ; ++k) {
// Compute the best price best[k] for a rod of length k.
best[k] = 0;
for (int i = 1 ; i <= k ; ++i)
best[k] = Max(best[k], prices[i] + best[k - i]);
}
return best[n]; // best price for a rod of length n
}Once again, this bottom-up solution is not a recursive function. Notice its double loop structure. Each iteration of the outer loop computes best[k], i.e. the solution to the subproblem of finding the best price for a rod of size k. To compute that, the inner loop must loop over all smaller subproblems, which have already been solved, looking for a maximum possible profit.
This version runs in O(N2).
Unfortunately our program only prints the maximum possible profit, not the size of each cut that is needed to achieve that profit. Next week we'll see how to modify the program to print the cut sizes as well.