Suppose you need to create a work plan, and each week you have to choose a job to undertake. The set of possible jobs is divided into low-stress and high-stress jobs.
If you select a low-stress job in week i, then you get a revenue of li dollars; if you select a high-stress job, you get a revenue of hi dollars. The catch, however, is that in order for you to take on a high-stress job in week i, it's required that you rest in weeki - 1 because you need a full week of prep time to get ready for the stress level (It's okay to choose a high-stress job in week 1.) On the other hand, you can take a low-stress job in weeki even if you have done a job (of either type) in week i-1.
So, given a sequence of n weeks, a plan is speci?ed by a choice of "low-stress", "high-stress" or "none" for each of the n weeks, with the constraint that if "high-stress" is chosen for week i> 1, then "none" must be chosen for week i - 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.)
Example: Suppose n=4, and the values of li and hiare given by the following table. Then the plan of the maximum value would be to choose "none" in week 1, a high stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0+50+10+10=70.
i Week 1 Week 2 Week 3 Week 4
l 10 1 10 10
h 5 50 5 1
Design a dynamic programming algorithm to find the value of the optimal plan. Implement your algorithm using any programming language you prefer. Describe the recurrence relation used by your algorithm at the top of your program or in a separate file.