You aim to get outside as much as possible this summer. Your two favorite activities are hiking the White Mountains and going to the beach on Cape Cod. Each weekend you chooose which of the two activites to partake in$.$ Hiking is your true favorite, but it is much more exhausting $,$ so if you go hiking one weekend, you$$ll be too tired to get off of the couch the following one $($even to go the beach!$).$ You have your friends$$ calendars and have looked at long$-$range weather forecast, and the goal is to decide each weekend whether to head to the mountains or hit the beach. On weekend i$,$ if you go hiking, you get value hi $>0,$ and if you go to the beach, you get value bi $>0.$ Recall, if you go hiking, then you cannot partake in either activity on weekend i $+1.$ Given a set of values h$1,$b$1,...,$hn$,$bn for n weekends, a schedule is a set of choices for each of the n weekends, where each weekend you can either chose $$hiking$,$beach$,$ or $$none$,$ and if you choose $$hiking$$ on weekend i$,$ then you must choose $$none$$ on weekend i$+1.$ The value of a schedule is the sum of the values of the activities you choose each weekend.Your goal is to design a dynamic programming algorithm that takes as input the n values h$1,$b$1,...,$hn$,$bn and computes an optimal schedule $($i$.$e$.$ a schedule with maximum value$).$

For example, if given the input:

Weekend $1$ Weekend $2$ Weekend $3$ Weekend $4$

b $3654$

h $71286$

the optimal schedule would be to go to the beach on weekend $1,$ hiking on weekends $2$ and $4,$ and staying on the couch on weekend $3,$ which has a value of $3+12+6=21.$

$($a$)$ Let OPT$($i$)$ be the maximum value you can get for doing the activities during weekends i$,$i$+1,...,$n$.$ Give a recurrence to compute OPT$($i$)$ from the values OPT$($i $+1),...,$OPT$($n$),$ and write the base case$($s$)$ for this recurrence. Write a few sentences explaining why your recurrence is correct.

$($b$)$ Using your recurrence, design a dynamic programming algorithm to output the optimal schedule of activities. You may use either a top$-$down or bottom$-$up approach. Remember that your algorithm needs to output the optimal schedule, not only its value. The output to your algorithm can be an array of length n in which the ith entry gives the choice made for weekend i in the optimal schedule $($this choice is one of $$beach$,$hiking$,$couch$).$

$($c$)$ Analyze the running time and space usage of your algorithm.Problem $3$

You aim to get outside as much as possible this summer: Your two favorite activities are hiking the White

Mountains and going to the beach on Cape Cod. Each weekend you chooose which of the two activites to partake

in$.$ Hiking is your true favorite, but it is much more exhausting, so if you go hiking one weekend, you'll be too

tired to get off of the couch the following one $($even to go the beach$1).$ You have your friends' calendars and have

looked at long$-$range weather farecast, and the goal is to decide each weekend whether to head to the mountains

or hit the beach. On weekend $i$ if you go hiking, you get value $h_i>0,$ and if you go to the beach, you get value $b_i>$

$0.$ Recall, if you go hiking, then you cannot partake in either activity on weekend $i+1.$ Given a set of values

$h_1,b_{1,\text{d}\text{o}\text{t}\text{s}\text{,}},h_0,b_u$ for $n$ weekends, a schedule is a set of choices for each of the $n$ weekends, where each weekend you

can either chose "hiking", "beach", or "none", and if you choose "hiking" on weekend $i,$ then you must choose

"none" on weekend $i+1.$ The value of a schedule is the sum of the values of the activities you choose each

weekend.Xour goal is to design a dynamic programming algorithm that takes as input the $n$ values $h,b_1,$dots,$h_0,b_n$

and computes an optimal schedule $($i$.$e$.$ a schedule with maximum value$).$

For example, if given the input:

the optimal schedule would be to go to the beach on weekend $1,$ hiking on weekends $2$ and $4,$ and staying on

the couch on weekend $3,$ which has a value of $3+12+6=21.$

$($a$)$ Let OPT$(j)$ be the maximum value you can get for doing the activities during weekends $\frac{ij+1,\text{d}\text{o}\text{t}\text{s}\text{,}n}{?}n.$ Give a

recurrence to compute OPT$(i)$ from the values OPT$(i+1)dots.\mathrm{.}0PT(n),$ and write the base case$($s$)$ for this

recurrence. Write a few sentences explaining why your recurrence is correct.

$($b$)$ Using your recurrence, design a dynamic programming algorithm to output the optimal schedule of

activities. You may use either a top$-$down or bottom$-$up approach. Remember that your algorithm needs

to output the optimal schedule, not only its value. The output to your algorithm can be an array of length