As a young entrepreneur looking to start a business, you learn that a long stretch of Huntington Avenue

has no bubble tea stores, but several empty store locations. The city has a constraint on bubble tea stores,

however: no two stores can be less than f feet of each other. You are interested in opening a chain of stores

along the road. One end of the road $($let us call it the $$west end$)$ already has a bubble store scheduled to

be opened by a rival entrepreneur. There are exactly n possible locations along the road for you to choose

from. The distances of the locations from the west end are given by an array d$[1...$ n$],$ where d$[$i$]$ is the

distance of the ith location from the west end. So $0<$ d$[1]<$ d$[2]<$ d$[3]<...<$ d$[$n$],$ and you are given

these distances in sorted order. Based on your CFO$$s analysis of the profitability of the stores, you have

computed a value array v where v$[$i$]$ is the value of opening a store at the ith location.

You would like to maximize the total value of the stores along the road you can open, subject to the constraint

that no two stores are at distance less than f $($note that this also includes the store at the west end$).$ Assume

that nobody else is building stores.

Your goal is to design a dynamic programming algorithm that takes input the n $+1$ values d$[1],$ d$[2],...,$ d$[$n$]$

and f and computes a set of stores that has optimal value.

$($a$)$ Let OP T $($i$)$ denote the maximum value you can get for opening stores in a subset of locations $1$ through

i$.$ Give a recurrence to compute OP T $($i$),$ and write the base case 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 set of stores to

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

to output the optimal set of stores, not only its value. Your algorithm may output the set of stores as

a list of its locations.

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

$($For full credit, the running time of your algorithm must be O$($n$^2)$; i$.$e$.,$ quadratic time or faster. You

will earn an extra credit of $2$ bonus points if your algorithm$$s running time is O$($n$)$ and you establish it

correctly in part $($c$)).$