Dynamic programming is a general technique that we can use to solve a wide variety of problems. Many (but not all) of these problems involve optimization, i.e. finding the shortest/longest/best solution to a certain problem.
Problems solvable using dynamic programming 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.
For an extended discussion of dynamic programming, see Introduction to Algorithms, ch. 15 "Dynamic Programming".
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, …
static int fib(int n) =>
n < 3 ? 1 : fib(n - 1) + fib(n – 2);What is this function's 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 + sqrt(5)) / 2
So fib runs in exponential time!
static int fib(int n, int[] cache) {
if (cache[n] == 0)
cache[n] = n < 3 ? 1 : fib1(n - 1) + fib1(n - 2);
return cache[n];
}
static int fib(int n) => fib1(n, new int[n + 1]);This memoized version runs in linear time, because the line
cache[n] = n < 3 ? 1 : fib1(n - 1) + fib1(n - 2);
runs only once for each value of i.
static 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.
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 price[i] be the price for selling a piece of size i. We want to compute profit(n), 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 price[i]. The maximum profit for dividing and selling the rest of the rod will be profit(n – i). So profit(n), i.e. the maximum profit for all possible partitions, will equal the maximum value for 1 ≤ i ≤ n of
price[i] + profit(n – i)
This solution runs in exponential time.
// Return the best price for cutting a rod of length n, given a table of length (n + 1)
// with the prices for pieces from lengths 0 .. n.
static int profit(int n, int[] prices) {
int best = 0;
for (int i = 1 ; i <= n ; ++i)
best = Max(best, prices[i] + profit(n - i, prices));
return best;
}This version runs in O(N2).
// Return the best price for cutting a rod of length n, given a table of length (n + 1)
// with the prices for pieces from lengths 0 .. n.
static int profit(int n, int[] prices) {
int[] best = new int[n + 1];
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
}This version also returns an array with the sizes into which the rod should be cut.
// Return the best price for cutting a rod of length n, given a table of length (n + 1)
// with the prices for pieces from lengths 0 .. n.
static int profit(int n, int[] prices, out int[] sizes) {
int[] best = new int[n + 1];
int[] cut = new int[n + 1];
for (int k = 1 ; k <= n ; ++k) {
best[k] = 0;
for (int i = 1 ; i <= k ; ++i) {
int p = prices[i] + best[k - i];
if (p > best[k]) {
best[k] = p;
cut[k] = i; // remember the best size to cut
}
}
}
List<int> l = new List<int>();
for (int s = n ; s > 0 ; s -= cut[s])
l.Add(cut[s]);
sizes = l.ToArray();
return best[n];
}We
want to write a method int
numCoins(int sum, int[] coins)
that
takes a integer and an array of coin denominations. The method should
determine the smallest number of coins needed to form the given sum.
A sum can contain an arbitrary number of coins of each denomination.
For example, if sum = 34 and coins = { 1, 15, 25 }, the method will
return 6, since
34 = 15 + 15 + 1 + 1 + 1 + 1
and it is not possible to form this sum with a smaller number of coins.
If
we cannot form the given sum using the given denominations of coins,
our method will return int.MaxValue.
This will run in exponential time.
// Return the smallest number of coins needed to form (sum).
static int numCoins(int sum, int[] coins) {
if (sum == 0) return 0;
int min = int.MaxValue;
foreach (int c in coins)
if (c <= sum)
min = Min(min, numCoins(sum - c, coins));
return min == int.MaxValue ? int.MaxValue : min + 1;
}This version runs in O(N2), where N = sum.
// Return the smallest number of coins needed to form (sum).
static int numCoins(int sum, int[] coins) {
int[] min = new int[sum + 1];
for (int k = 1 ; k <= sum ; ++k) {
// Compute min[k], the minimum number of coins needed to add up to k.
int m = int.MaxValue;
foreach (int c in coins)
if (c <= k)
m = Min(m, min[k - c]);
min[k] = m == int.MaxValue ? int.MaxValue : m + 1;
}
return min[sum];
}This version returns an array with the values of the coins that form the sum.
static int[] numCoins2(int sum, int[] coins) {
int[] min = new int[sum + 1];
int[] first = new int[sum + 1];
for (int k = 1 ; k <= sum ; ++k) {
// Compute min[k], the minimum number of coins needed to add up to k.
// Also remember first[k], the first coin to use in forming the sum k.
int m = int.MaxValue;
foreach (int c in coins)
if (c <= k && min[k - c] < m) { // best so far
m = min[k - c];
first[k] = c;
}
min[k] = m == int.MaxValue ? int.MaxValue : m + 1;
}
List<int> l = new List<int>();
for (int s = sum ; s > 0 ; s -= first[s])
l.Add(first[s]);
return l.ToArray();
}