For this dynamic programming problem and the next one, be sure to (a) define and describe the subproblem; (b) write the recurrence relation for the subproblem, including the base case(s); (e) write pseudo codes showing how a table for the subproblems is filled (i.e., by the bottom up" approach).

The residents of the underground city of Zion defend themselves through a combination of kung-fu, heavy artillery, and efficient algorithms. Recently, they have become interested in automated methods that can help fend off attacks by swarms of robots. Heres what one of these robot attacks look like: A swarm of robots arrives over the course of n seconds; in the ilh second, xi robots arrive. Based on remote sensing data, you know this sequence 11, 12, ... , ln in advance. You have at your disposal an electromagnetic pulse (EMP), which can destroy some of the robots as they arrive; the EMPs power depends on how long its been allowed to charge up. To make this precise, there is a function f(-) so that if j seconds have passed since the EMP was last used, then it is capable of destroying up to fG) robots. So, specifically, if it is used in the kth second, and it has been j seconds since it was previously used, then it will destroy min[Ik, f()] robots. (After this use, it will be completely drained.) We will also assume that the EMP starts off completely drained, so if it is used for the first time in the juh second, then it is capable of destroying up to f() robots. Given the data on robot arrivals X = (11,12, ... , In), and given the recharging function f(-), the problem is to determine the maximum number of robots that can be destroyed by activating the EMP at certain points in time. For example, suppose n = 4, X = (1, 10, 10,1) and f(-) = (1,2,4,8). The best solution would be to activate the EMP in the 3rd and 4th seconds. In the 3rd second, the EMP has gotten to charge for 3 seconds, and so it destroys min(10,4)=4 robots. In the 4th second, the EMP has only gotten to charge for 1 second since its last use, and it destroys min(1,1)=1 robot. This is a total of 5. [10 points)