You are going for a vacation to France. Before your trip, you chose $n$ attractions you want to visit

and picked a specific order in which you want to visit them. In your list, the coordinates of attraction

i are stored in variable point $[$i$].$ The starting and ending points of your journey are the same.

When you arrived to Paris, you realize that you cannot visit all attractions, because the maximum

distance you are willing to travel from one attraction to the next attraction is maxDistance. So

you would like to remove some of the attractions from your list so that the distance between two

consecutive attractions is at most maxDistance. Design and implement an algorithm that finds the

maximum number of attractions you can visit. Note that

The algorithm cannot change the order in which you visit attractions. It can only skip some

attractions on the list.

Your trip must start and finish at location $(0,0).$ There is no attraction at the location.

If you visit attraction $B$ right after visiting attraction $A,$ the distance between A and $B$

must be at most maxDistance $>0.$ Similarly, if you travel between the point $(0,0)$ and an

attraction, the distance must be at most maxDistance.

The distance between two points $p$ and $q$ equals $\sqrt[\phantom{2}]{(p*x-q*x{)}^2+(p*y-q*y{)}^2}.$Please do the following:

$$ Formulate the subproblem. Please state it as precisely as possible.

$$ Design a dynamic programming algorithm for solving this problem:

$$ State the base case.

$$ State the recurrence relation.

$$ Explain why the recurrence relation is correct.

$$ Please provide the pseudocode. Please use the bottom$-$up approach.

$$ Explain:

$$ What is the running time of your algorithm.

$$ How to recover the minimum total cost.

$$ How to recover the set of the purchased towers $($and which towers are purchased

with coupons$).$ You don$$t need to write a pseudocode.

$$ Why your algorithm correctly handles the case when an optimal solution doesn$$t

exist.