Dynamic Programming Cheapest Train Ride Question

Question

I am struggling with the below dynamic programming practice problem and I am hoping someone can help. The problem states:

"You want to go from station 1 to station n by rail. The train fare from station i to station j is F(i, j). You want to break your trip up into a series of segments in order to minimize the cost, but each segment must go in the forward direction, i.e., from station i to station j for i < j. Design an efficient dynamic programming algorithm for doing this and analyze its running time."

Now, my thought would be that we would want to use a top-down approach. We start with some possible first choice from the starting station to some other station, then we recursively test all the different options. The recurrence relation would likely be something along the lines of picking the next possible segment that has the lowest fare.

Any help on this would be greatly appreciated!

Answer 1

Let $V(i)$ be the minimum cost to get from station $i$ to station $n$. Then $V(n)=0$, and for $i<n$, the dynamic programming recursion ("Bellman's equation") is $$V(i) = \min_{j>i} (F(i,j)+V(j)).$$ You want to compute $V(1)$, which you can do by computing $V(i)$ for $i=n$ to $1$ (in decreasing order of $i$).