[Solved]: Dynamic Programming Travel Planning Problem

Problem Detail: 

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

Asked By : guest

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44758