$$ Details

You start on a trip at mile marker $a_0=0$ and wish to reach the hotel at mile marker $a_{n-1}.$ Between mile markers $0$ and $a_{n-1},$ there are $n-2$ hotels at mile markers $a_1,a_2,$dots,$a_{n-2}.$ You can stop at any of these hotels along the way, but you must ultimately stop at the final hotel. Traveling from mile marker $a_i$ to $a_j$ incurs a penalty of penalty $(i,j).$ Thus, the total penalty for a sequence of stops

$a_{i_0}=a_0{a}_{i_1}{a}_{i_2}$cdots$a_{l-2}{a}_{n-1}=a_{i_l-1}$

is given by

penalty $(0,i_1)+$penalty$(i_1,i_2)+$cdots$+$penalty$(i_{l-2},i_{n-1})$

Design a dynamic programming algorithm to minimize the total penalty to travel from hotel $0$ to hotel $n-1.$

Define the subproblems for your solution.

Give a recursive formulation to solve the subproblems. Include the base cases.

Give pseudocode for a memoized, top$-$down algorithm that outputs this maximum.

Give pseudocode for an efficient, bottom$-$up algorithm that outputs this maximum.

What is the runtime of your solution? Justify your answer.

Explain how to modify your algorithm to also output the optimal sequence of hotels.