Dynamic Programming Travel Planning Problem
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.