Dynamic Programming Travel Planning Problem

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

• What have you tried? Have you considered adding an extra parameter $Cost(x,i,...)$? – Tom van der Zanden Jul 26 '15 at 19:21
• I was thinking I could maybe keep track of how many plane trips there were so I could tell if there were n/2 of them, but once I do have n/2 of them I don't know how to keep getting optimal results. – guest Jul 26 '15 at 19:27
• Another alternative I'm thinking about is instead of adding the next optimal travel mode, starting with a trip with all trains and adding in plane trips one at a time into their optimal positions. I'm having trouble writing a recurrence relations for this though. – guest Jul 26 '15 at 19:31
• I noticed you've edited the question to add your solution, and you seem to want us to check whether your solution is correct. I regret to inform you that "please check my solution" questions are not suitable for this site. They admit only a yes/no answer, which isn't likely to be useful to anyone else (and possibly not even to you). If you are taking a course, you might ask your teaching assistant or grader, but that kind of question is considered off-topic for this site. – D.W. Jul 28 '15 at 22:46
• Ok, I'll keep that in mind. Thanks for letting me know. – guest Jul 28 '15 at 22:50

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.
• @guest now your $Cost(x,i)$ function says - "what is the minimum cost to travel from city 0 to city $i$ and in last city have/haven't transfer of type $x$". Yuval suggest to enhance this dynamic to: $Cost(x,i, t)$ that will answer to question - "what is the minimum cost to travel from city 0 to city $i$ by using exactly $t$ plane rides and $i - t$ train rides and in last city have/haven't transfer of type $x$". – knok16 Jul 26 '15 at 21:26