Suppose you are managing a consulting team of expert computer hackers, and each week you have to choose a job for them to undertake. 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 the dean’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-stress job in week i, it is 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 is 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 is 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.) 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 an optimal plan.

What would a recursive dynamic programming solution to this be?