Testing the Catcher: More Dynamic Programming
Here's the problem:
You are testing an anti-missile "catcher." Once it is launched, it can catch any missile coming at it that is at an altitude less than or equal to it. Thereafter, it can continue to catch missiles, that come at it, but it can never increase in altitude. Given a list of altitudes of incoming missiles, determine the maximum number of missiles that can be caught by the "catcher." Assume that the catcher starts at an altitude higher than that of any of the missiles that will eventually come at it.
Here's a short example, give the list
80, 70, 60, 50, 65, 45, 60, 61
we find we can catch at most 5 missiles, namely:
80, 70, 60, 50 and 45.
First we will characterize the problem recursively, and solve it that way. Then we will edit our solution to utilize dynamic programming. Finally, we will run both of the solutions to show how the dynamic programming solution is faster for larger data sets.
Recursive Solution
If you read this carefully, this problem is really a longest non-increasing sequence problem.
The recursive solution is as follows:
For the first value in the list, we have two options: (a) take it, (b) don't take it
Work out which of these two options is better and return the maximum of the two strategies.
Our recursive function takes in four parameters:
1) The whole list
2) The size of the list
3) The index of the current value we are considering
4) The height of the last missile taken previous to the current.
One thing to note is that sometimes, the current missile can not be intercepted. This is precisely when its height is greater than the height of the previous missile intercepted.
Initially, the last parameter is set to a value greater than the height of any missile.
In the code, if it's possible to intercept the current missile, then take the maximum of:
1) 1 + maximum number of missiles that can be intercepted from the rest of the list such that the maximum height is that of the current missile.
2) the maximum number of missiles that can be intercepted from the rest of the list such that the maximum height is that of the previous missile taken.
Here is the code (in C++, sorry!)
int findmax(int *list, int size, int start, int maxh) {
// No list at all to consider.
if (start >= size)
return 0;
// The current missile can be considered, it's low enough.
if (list[start] <= maxh)
// The first option is to take the missile, if you do this the
// new height of the catcher is list[start]
// If you don't do this you just continue to the next missile
// but stay at the same height.
return max (1+findmax(list, size, start+1, list[start]),
findmax(list, size, start+1, maxh));
// Can't consider the current missile; move to the next.
else
return findmax(list, size, start+1, maxh);
}
Dynamic Programming Solution
Now, the question is, how can we turn this into DP?
For each sublist starting from the beginning, perhaps we could store the maximum number of missiles that can be intercepted from that sublist. Thus, for the list:
0 1 2 3 4 5 6 7
80 / 70 / 60 / 50 / 65 / 45 / 60 / 61We could store (in an auxiliary array) the values:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 4 / 5 / 5 / 5The key to DP is being able to construct this table just using previously filled in values to the table. The problem here is just because we know that the longest list using the first 7 elements (in indexes 0 through 5) is 5, doesn't mean we can decide whether or not we can do better using the last element, 61.
This is because we DON'T know the height of the last missile taken!!! The critical information is whether or not that last missile was taken at an altitude of 61 or greater.
In fact, the information we need is what was the height of the last missile in the list of four intercepted missiles. If this is greater than or equal to 61, then we can add 61 to the list, otherwise we can't.
So, we have two options:
1) Store the last missile height the corresponds to each of the longest sequences
2) Stipulate that the entry in the array corresponds to the longest sequence of missiles that can be intercepted with the LAST missile being intercepted.
It turns out that the characterization for choice 2 works quite well. (1 would work as well, I believe, but you'd have to store pairs of values in each element of the table instead of just one value.) Here is the adjusted auxiliary array if we choose to store this information:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 3 / 5 / 4 / 3To finish up the problem, we simply find the maximum value stored in this auxiliary array.
Now, how do we construct this auxiliary array?
We will fill in each value one by one, in order.
When we fill in the kth element, we must ask ourselves the following question:
Assuming that the last missile intercepted was any of the previous, which of these previous interceptions leads to the maximum number of missile interceptions that end with this current missile?
Here's an example:
Consider filling out the last element in the auxiliary array for the example above.
For each previous missile that is at a height greater than or equal to 61, we must find the one that gives us the maximum number of intercepted missiles.
01 2 3 4 5 6 7
80 / 70 / 60 / 50 / 65 / 45 / 60 / 61Our auxiliary array will initially look like this. The first entry is one because we can always take exactly one missile out of the first one regardless of its height.
01 2 3 4 5 6 7
1 / 0 / 0 / 0 / 0 / 0 / 0 / 0Now, to fill in array element 1, we look at the current missile which is of height 70. We must consider all previous array elements. In particular, we must only find those with a missile height of 70 or greater. This corresponds to array element 0. The 1 in this slot represents that there is a sequence of length 1 that ends in 80 up to that point. If we tack on the 70, then we get a sequence of length 2. This is better than the alternative of having 70 in the sequence by itself, so now we have:
01 2 3 4 5 6 7
1 / 2 / 0 / 0 / 0 / 0 / 0 / 0Quickly, it can be seen that the array will fill up as follows:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 0 / 0 / 0 / 0Now, let's consider determining index 4. The corresponding missile height is 65. The only two previous entries that have a number greater than or equal to 65 are indexes 0 and 1. We take the maximum of these, which is 2, and then add 1. The reason is as follows: There is a sequence of length 2 that ends in 70 (that's what the 2 in index 1 means), thus, we can tack on a 65 to the end of this sequence to get a sequence of length 3. So now we have:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 3To fill in index 5, notice that its missile height 45 is less than the missile height of index 3, which is 50. Furthermore, we know there is a sequence of missiles of length 4 that ends with fifty, so we can tack on the 45 to get a sequence of length 5:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 3 / 5Next, we find all indexes that correspond to missiles of height 60 or more (since that is the current missile height.)
These are indexes 0, 1, 2, and 4. The maximum value stored in these indexes is 3, thus, the longest sequence that ends with this 60 is of length 4. (It is the sequence 80, 70, 60, 60.) Here is the adjusted array:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 3 / 5 / 4Finally, let's consider adding the last missile of height 61:
We will loop through the array of missile heights, checking to see if those missiles are at height 61 or higher. There are only three, in indexes 0, 1 and 4. For these three missiles, we check the corresponding entry in the auxiliary array. We see that if 80 is the last missile we take, then by taking 61, we have taken 2 missiles. But then we see that if we take 70 as our last missile, by taking 61 afterwards, we have taken 3 missiles. Finally, if we take 65 as our last missile, we have taken 2 missiles, so adding 61 gives a final length of 4. Thus, the longest possible sequence that ends in this 61 is of length 4:
01 2 3 4 5 6 7
1 / 2 / 3 / 4 / 3 / 5 / 4 / 4At the end, we must scan the whole array for the largest value. This is 5, the length of the longest non-increasing sequence in the list of values.