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})$
