There was no lecture or tutorial this week.
Our topic this week is dynamic programming, continued.
You can read about dynamic programming in chapter 15 "Dynamic Programming" of Introduction to Algorithms.
Here are some more notes on the subject:
Last week we began our study of dynamic programming. The dynamic programming problems we saw last week had a 1-dimensional structure. That means that each of those problems could be solved by writing a recursive function with 1 argument. The naive recursive solution was exponentially inefficient, since it solved the same subproblems over and over again. We found that we could solve these problems much more efficiently by filling in a 1-dimensional array in a certain order. This array recorded the solution to each subproblem, so that it was immediately available to use in solving other, larger, subproblems.
For example, last week we studied the rod-cutting problem. The naive recursive solution looked like this:
// Return the best price for cutting a rod of length n, given a table
// with the prices for pieces from lengths 1 .. 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;
}Notice that profit() is a function of a single argument "int n" (ignoring the constant array prices[], which could just be stored as a field outside the function). To compute the result more efficiently, we used a bottom-up approach that filled in a 1-dimensional array called best[], where best[i] held the best possible profit for a rod of size i, i.e. the value that would be returned by profit(i, prices).
This week we will study slightly more challenging dynamic programming problems that have a more general 2-dimensional structure. For these problems, a naive recursive solution will be a function with 2 arguments. Once again, this naive solution will run in exponential time. We can solve these problems more efficiently using bottom-up dynamic programming in which we fill in a 2-dimensional array or array-like data structure. We will need to be careful about the order in which we fill in the array elements. The solution to any subproblem instance will depend on the solutions to smaller instances, so we need to fill in the array in some order that guarantees that the dependent solutions will already be available when we compute any subproblem solution.
As always, some examples will make these ideas clearer. Let's consider the problem of finding the longest palindromic subsequence of a given string. For example, consider the string "watermelon stew". The string "wteretw" is a longest palindromic subsequence:
W A T E R M E L O N S T E W W T E R E T W
That's because this subsequence is a palindrome (i.e. it reads the same forwards and backwards), and there is no longer palindromic subsequence in the string. Note that the longest palindromic subsequence is not necessarily unique: "wtemetw" is another possibility.
We can solve this problem using two-dimensional dynamic programming. Suppose that the input string s has length N, with character indices from 0 to (N - 1). Let L(i, j) be the length of the longest palindromic subsequence of s[i .. j].
We must first find a recursive formulation of the problem that will allow us to compute L(i, j) recursively for any i and j. Our base case is straightforward: if i = j, then clearly L(i, j) = 1, since any 1-character string is a palindrome. In fact it will be useful to have an additional base case that is even smaller: if j < i, then s[i .. j] is empty, so L(i, j) = 0.
Now suppose that i < j, which will be the recursive case. We may consider two possibilities:
First suppose that s[i] = s[j] = c for some character c. Let P be any longest palindromic subsequence of s[(i + 1) .. (j – 1)], and let Q = cPc. Then certainly Q is a palindomic subsequence of s[i .. j]. Furthermore, no palindromic subsequence of s[i .. j] can be longer than Q. To see this, suppose that R is a palindromic subsequence of s[i .. j] that is longer than Q. If R = cSc for some character c, then S must be a palindrome and must also be a subsequence of s[(i + 1) .. (j – 1)] that is longer than P, which is a contradiction. Otherwise, if R does not begin and end with c then R itself must be a subsequence of s[(i + 1) .. (j – 1)] that is longer than P, which is also a contradiction.
So we see that Q is a longest palindromic subsequence of s[i .. j]. And so
L(i, j) = L(i + 1, j – 1) + 2
Now suppose that s[i] ≠ s[j]. Then the longest palindromic subsequence of s[i .. j] does not include both s[i] and s[j], since if it did, it would begin with s[i] and would end with s[j] and would not be a palindrome. Therefore the longest palindromic subsequence of s[i .. j] must either be a palindromic subsequence of s[i .. j – 1], or of s[i + 1 .. j] (or possibly of both). So in this case
L(i, j) = max(L(i, j – 1), L(i + 1, j))
Since we have found a recursive pattern, we may now write a recursive function to compute L(i, j):
// Compute the length of the longest palindromic subsequence of s[i .. j].
static int len(string s, int i, int j) {
if (j < i) return 0;
if (i == j) return 1;
return s[i] == s[j] ? len(s, i + 1, j - 1) + 2
: Max(len(s, i, j - 1), len(s, i + 1, j));
}It works:
string s = "watermelon stew"; WriteLine(lpsLength(s, 0, s.Length – 1)); // writes 7
However this function will run in exponential time.
To solve this problem more efficiently, we will use bottom-up dynamic programming to fill in a 2-dimensional array len[], where len[i, j] = L(i, j). As mentioned above, we need to be careful about the order in which we fill in the array. Specifically, when we compute len[i, j] we must already know len[i + 1, j] and len[i, j – 1] and len[i + 1, j – 1]. An illustration will help here. Supposed that s = "india". Here is a table showing the values of len[i, j]:
Notice the following:
Every entry on the diagonal is 1, since len[i, i] = 1 for all i.
Every entry below the diagonal is 0, since len[i, j] = 0 whenever j < i.
len[0, 3] = 3, since the longest palindromic subsequence of s[0 .. 3] = "indi" has length 3. When we recursively compute len[0, 3], we will need the values of len[0, 2], len[1, 2] and len[1, 3], as illustrated by the arrows above. I've only drawn these arrows for this one cell, but all cells in the table will have the same dependency pattern.
len[0, 4] = 3. This is the top-level answer we are seeking.
Now, we certainly cannot fill in this rows in this table from top to bottom, because then as we computed each row we would not already have the values below it. One possible order for filling in the rows is bottom to top, left to right:
When we fill in this order, as we encounter each cell (i, j) we will already know the value of its neighbors below, to the left, and diagonally below and to the left. And so we will be able to compute len[i, j].
Now, there is really no need for us to iterate over all the cells below the diagonal in the table above, since they all have value 0 and will be initialized to that value when we create our array. So instead we can fill in the table from bottom to top, proceeding rightward from the diagonal position in each row:
We now have a strategy, so let's write code to fill in the array:
// Compute the length of the longest palindromic subsequence of s.
static int longestPalindromic(string s) {
// len[i, j] is the length of the longest palindromic subsequence of
// s[i .. j].
int[,] len = new int[s.Length, s.Length];
int i, j;
for (i = s.Length - 1 ; i >= 0 ; --i) {
len[i, i] = 1;
for (j = i + 1 ; j < s.Length ; ++j)
len[i, j] =
s[i] == s[j] ? len[i + 1, j - 1] + 2
: Max(len[i, j - 1], len[i + 1, j]);
}
return len[0, s.Length - 1];
}Our function will run in O(N2), where N = s.Length. This is a huge improvement over the exponential version.
Of course, we may want to know not only the length of the longest palindromic subsequence, but also the subsequence itself! So we'd like to extend our code to return that string. Here is one possible approach: after we have filled in the table above we can use the values in it to reconstruct the string we want. To do that, we start at the upper right, i.e. the value len[0, s.Length – 1]. We can reconstruct a path through the table that explains how that value was derived, and that path will reveal the string itself. At any cell (i, j), if s[i] == s[j] then we know that s[i] and s[j] are included in the string we want, and we can record those characters and proceed to (i + 1, j – 1). Otherwise, we proceed either to (i, j – 1) or to (i + 1, j), choosing the cell with the larger value. Here is an extended version of the function above that can reconstruct the string in this way:
// Compute the longest palindromic subsequence of s.
static string longestPalindromic(string s) {
// len[i, j] is the length of the longest palindromic subsequence of
// s[i .. j].
int[,] len = new int[s.Length, s.Length];
… same code as above for filling in the table …
// Now len[0, s.Length - 1] is the length of the longest palindromic
// subsequence. We now want the subsequence itself. We need to build
// the sequence from the outside inward, so we use two strings a and b
// and will return (a + b).
string a = "", b = "";
i = 0;
j = s.Length - 1;
while (j >= i) {
if (j == i) {
a += s[i];
break;
}
if (s[i] == s[j]) {
a = a + s[i];
b = s[j] + b;
++i;
--j;
} else if (len[i, j - 1] > len[i + 1, j])
--j;
else ++i;
}
return a + b;
}Study the function to understand how it works.
This code for constructing the longest palindromic subsequence may seem like a chore, and so you may be wondering if there is an easier way. Actually there is. When we build the table, instead of storing the length of the longest palindromic subsequence of s[i .. j] in each table cell, we can store the longest palindromic subsequence itself:
// Compute the longest palindromic subsequence of s.
static string longestPalindromic(string s) {
// p[i, j] is the longest palindromic subsequence of s[i .. j].
string[,] p = new string[s.Length, s.Length];
int i, j;
for (i = s.Length - 1 ; i >= 0 ; --i) {
p[i, i] = s[i].ToString();
for (j = i + 1 ; j < s.Length ; ++j)
if (s[i] == s[j])
p[i, j] = s[i] + p[i + 1, j - 1] + s[j];
else {
string t = p[i, j - 1], u = p[i + 1, j];
p[i, j] = t.Length > u.Length ? t : u;
}
}
return p[0, s.Length - 1];
}That was easier! This seems like a nicer solution for this problem.
For some other dynamic programming problems, however, it may be easier or more efficient to store intermediate values in the table and the reconstruct the final solution at the end. (Actually we did that for a couple of one-dimensional dynamic programming problems last week.)
Let's look at another classic problem that we can solve using two-dimensional dynamic programming: the subset sum problem. Given a set of positive integers and an integer k, we wish to determine whether any subset of the given set has sum k.
As usual, we'd first like to come up with a recursive formulation of the problem. As a clue to how to do that, recall how a couple of weeks ago we wrote a function that generated all subsets of a given set. Here is the general approach we took. Given a set S, we can take any element x from the set, and let S' be the remaining elements in S. If we recursively generate all subsets of S', then each subset is itself a subset of S. In addition, we can add x to any of those subsets to form a subset of S.
So now suppose that we are given a set of positive integers S and an integer k, and we'd like to know whether any subset of S has the sum k. Take any integer x from S, and let S' be the remaining integers in S. If any subset of S' has sum k, then that is a subset of S which has sum k. In addition, if any subset of S' has sum (k – x), then we can add x to that subset to obtain a subset of S which has sum k.
We can use this idea to solve the problem recursively:
// Return true if any subset of a[0 .. (i - 1)] has sum k.
static bool hasSum(int[] a, int i, int k) {
if (k == 0)
return true; // the empty set is a subset, and has sum k
if (i == 0)
return false; // set is empty, cannot have non-zero sum
return hasSum(a, i - 1, k) // we can make k without a[i - 1]
|| a[i - 1] <= k &&
hasSum(a, i - 1, k - a[i - 1]); // we can make k by adding a[i - 1]
}
static bool hasSum(int[] a, int k) => hasSum(a, a.Length, k);As usual, this native recursive solution may take exponential time to run.
The function hasSum above takes two parameters i
and k (in addition to the constant array a). That is a sign that we
can solve this problem using two-dimensional dynamic programming. We
will
need a two-dimensional array that holds the boolean
value hasSum(a, i, k) for every possible value of i and
k. In our bottom-up implementation, we will also call this array
hasSum. Specifically, hasSum[i, k] will be true if any
subset of a[0 .. (i – 1)] has sum k, just like in the
recursive function above.
Once again we must consider the order in which we
will fill the array elements. When we compute hasSum[i, k],
we may need to know the value of hasSum[i – 1, j] for
any value j in the range 0 <= j <= k. That shows that we should
fill the array in increasing order of i. It does not matter whether
we fill each array column in increasing or decreasing order of k,
since the computation of hasSum[i, k] does not depend on any other
values in the same column.
After we have filled in the array, if it turns out
that there was some subset with sum k, we would like to generate that
subset. As in other dynamic programming problems, we can use an
iterative loop to reconstruct the solution from the array. At
the beginning of each loop iteration, we have values
i and k such that hasSum[i, k] is true, so
we know that some subset of a[0 .. (i - 1)]
has sum k.
If
hasSum[i - 1, k] is
also true, then we
can make the sum k without using a[i - 1].
So we can simply subtract 1 from i, then proceed to the next loop
iteration.
Otherwise hasSum[i -
1, k] is false,
and we need to use
a[i – 1] in
our set that adds up to k. In this case hasSum[i
- 1, k - a[i - 1]] must be true, since there must be some
subset of a[0 .. (i - 2)]
that adds up to k - a[i - 1], to give us the
remaining part of the sum. So we can decrement i and subtract a[i
- 1] from k, then proceed to the next loop iteration.
Combining these ideas, here is our bottom-up solution:
// Does any subset of the integers in a have sum s? If so, return the subset;
// otherwise return null.
static int[] subsetSum(int[] a, int s) {
// hasSum[i, k] is true if some subset of a[0 .. (i - 1)] adds up to k.
bool[,] hasSum = new bool[a.Length + 1, s + 1];
hasSum[0, 0] = true; // we can make 0 from the empty set
for (int i = 1 ; i <= a.Length ; ++i)
for (int k = 0; k <= s ; ++k)
hasSum[i, k] = hasSum[i - 1, k] // we can make k without a[i - 1]
|| a[i - 1] <= k &&
hasSum[i - 1, k - a[i - 1]]; // we can make k by adding a[i - 1]
if (!hasSum[a.Length, s])
return null; // sum is not possible
// Now construct the integers in the set.
List<int> result = new List<int>();
for (int i = a.Length ; i > 0 ; --i) {
if (!hasSum[i - 1, s]) {
result.Add(a[i - 1]);
s -= a[i - 1];
}
}
return result.ToArray();
}
Once again, you may feel that having to reconstruct the solution at
the end is a bother. Is there an easier way? Well, just as in the
previous exercise we could store the solutions themselves in
the array we are filling in. For
example, instead of a two-dimensional array of
booleans, we could store a two-dimensional array of List<int>:
List<int>[,] sumSet = new List<int>[a.Length + 1, s + 1];
And then for any i and k, if there is a subset of a[0 .. i - 1]
whose sum is k, then sumSet[i, k] could hold a list of
integers containing that subset, and could otherwise be null.
However this solution would be relatively inefficient. If we use lists to represent sets, then every time we want to construct a list that contains all the elements in a previous set plus a new integer, we must make a copy of the previous list. If the problem instance was large, all of these list copies could take a significant amount of time and memory.
If, however, we represent sets using linked lists rather than List objects (which are really arrays), then no copying would be necessary, since we can prepend an element to a linked list (while leaving the existing list intact) in O(1). So that would be a reasonable solution, and you may want to try to code that up as an exercise. Of course, even that solution would be less efficient than our solution above, since it is hard to beat an array of booleans if you are trying to save space or time. :) So is it worth using linked lists to avoid the extra loop at the end of the method above? You can make your own judgment about that. :)