You want to visit n cities: $0  1  2      n$. For traveling between city $i$ and $i + 1$ $(0  i < n) $ you need to choose between two modes of transportation: train or plane. You are starting at the train station of city $0$ and want to end up at the airport of city $n$. The cost of transferring between the train station and the airport of city $i$, either direction, is $b_i$. The cost of traveling from city $i$ to city $i+1$ via train is $t_i$ and by plane $p_i$.You need to use to use the plane and train exactly $n/2$ times. Assume that $n$ is divisible by $2$.Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.What I have so far is what I think is a solution to the problem without considering the $n/2$ constraint.$Cost(x, i, y) = \begin{cases} \begin{cases}t_i & y=0\\ p_i + b_i & i-y=0 \end{cases} & i=1 \\ min\begin{cases} \begin{cases} min\begin{cases}p_i + Cost(P, i-1,y-1) \\ p_i + b_i + Cost(T, i-1,y-1) \end{cases} & y > 0 \\ inf & y=0 \end{cases} \\ \begin{cases} min\begin{cases} t_i + Cost(T, i-1,y)\\ t_i + b_i + Cost(P, i-1,y) \end{cases} & i-y > 0\\ inf & i-y = 0\end{cases}  \end{cases} & 1 < i < 0  \\ min\begin{cases}p_i + Cost(P, i-1,y-1) \\ t_i + b_i + Cost(T, i-1,y) \end{cases}  & i=n \end{cases}$The values of $x$ correspond to different scenarios for which station at $i$ you are located at.$x = P$ $x = T$ The value of $y$ is the number of plane rides and $i-y$ is the number of train rides $0 \le y \le i$To get the optimal cost with $n/2$ plane rides you would call $Cost(x,i,\frac{x}{2})$
Dynamic Programming Travel Planning Problem
algorithms;dynamic programming
Hint: For each $0 \leq i \leq n$ and $0 \leq t \leq i$, calculate the optimal route between city $0$ and city $i$ using $t$ plane rides and $i-t$ train rides.