Dynamic Programming
Suppose you're managing a consulting team of expert computer hackers, and each week you have to choose a job for them to undertake. As you can well imagine, the set of possible jobs is divided into those that are low-stress (e.g. setting up a Web site for a class at the local elementary school) and those that are high-stress (e.g., protecting te nation's most valuable secrets.) The basic question each week is whether to take on a low-stress job or a high-stress job. If you select a low-stress job for your team in week i, then you get a revenue of li > 0 dollars; if you select a high-stress job, you get a revenue of hi > 0 dollars. High-stress jobs typically pay more. The catch, however, is that in order for the team to take on a high-stess job in week i, it's required that they do no job (of either type) in week i - 1; they need a full week of prep time to get ready for the crushing stress level. On the other hand, it's okay for them to take a low-stress job in week i even if they have done a job (of either type) in week i-1. So, given a sequence of n weeks, a plan is specified by a choice of "low-stress", "high-stress" or "none" for each of the n weeks, with the property that if "high-stress" is chosen for week i > 1, then "none" has to be chosen for week i - 1. (It's okay to choose a high-stress job in week 1.) The value of the plan is determined in the natural way; for each i, you add li to the value if you choose "low-stress" in week i, and you add hi to the value if you choose "high-stress" in week i. (You add 0 if you choose "none" in week i.) The problem. Given sets of values l1, l2, . . . , ln and h1, h2, . . . , hn, find a plan of maximum value (such a plan is called optimal.) Give an efficient algorithm to take the input values and return the value of the optimal plan.