Minimum number of train station stops

I don't think you need dynamic programming at all for this problem. It can basically be expressed by binary calculations.

If you convert the number of a station to binary it tells you right away how to get there from station 0, e.g.,

station 6 = 110

tells you that you need to take the n=3 train and the n=2 train each for one station. So the popcount of the binary representation tells you how many steps you need.

The next step is to figure out how to get from one station to another. I´ll show this again by example. Say you want to get from station 7 to station 23.

station 7 = 00111

station 23 = 10111

The first thing you want to do is to get to an intermediate stop. This stop is specified by

(highest bits that are equal in start and end station) + (first different bit) + (filled up with zeros)

In our example the intermediate stop is 16 (10000). The steps you need to make can be calculated by the difference of that number and the start station (7 = 00111). In our example this yields

10000 - 00111 = 1001

Now you know, that you need 2 stops (n=1 train and n=4) to get from 7 to 16. The remaining task is to get from 16 to 23, again this can be solved by the corresponding difference

10111 - 10000 = 00111

So, you need another 3 stops to go from 16 to 23 (n= 3, n= 2, n= 1). This gives you 5 stops in total, just using two binary differences and the popcount. The resulting path can be extracted from the bit representations 7 -> 8 -> 16 -> 20 -> 22 -> 23

Edit:

For further clarification of the intermediate stop let's assume we want to go from

station 5 = 101 to

station 7 = 111

the intermediate stop in this case will be 110, because

highest bits that are equal in start and end station = 1

first different bit = 1

filled up with zeros = 0

we need one step to go there (110 - 101 = 001) and one more to go from there to the end station (111 - 110 = 001).

About the intermediate stop

The concept of the intermediate stop is a bit clunky but I could not find a more elegant way in order to get the bit operations to work. The intermediate stop is the stop in between start and end where the highest level bit switches (that's why it is constructed the way it is). In this respect it is the stop at which the fastest train (between start and end) operates (actually all trains that you are able to catch stop there).

By subtracting the intermediate stop (bit representation) from the end station (bit representation) you reduce the problem to the simple case starting from station 0 (cf. first example of my answer).

By subtracting the start station from the intermediate stop you also reduce the problem to the simple case, but assume that you go from the intermediate stop to the start station which is equivalent to the other way round.

I will attempt to prove my algorithm is optimal.

The algorithm is "take the fastest train that doesn't overshoot your destination".

How many stops this is is a bit tricky.

Encode both stops as binary numbers. I claim that an identical prefix can be neglected; the problem of going from a to b is the same as the problem of going from a+2^n to b+2^n if 2^n > b, as the stops between 2^n and 2^(n+1) are just the stops between 0 and 2^n shifted over.

From this, we can reduce a trip from a to b to guarantee that the high bit of b is set, and the same "high" bit of a is not set.

To solve going from 5 (101) to 7 (111), we merely have to solve going from 1 (01) to 3 (11), then shift our stop numbers up 4 (100).

To go from x to 2^n + y, where y < 2^n (and hence x is), we first want to go to 2^n, because there are no trains that skip over 2^n that do not also skip over 2^n+y < 2^{n+1}.

So any set of stops between x and y must stop at 2^n.

Thus the optimal number of stops from x to 2^n + y is the number of stops from x to 2^n, followed by the number of stops from 2^n to 2^n+y, inclusive (or from 0 to y, which is the same).

The algorithm I propose to get from 0 to y is to start with the high order bit set, and take the train that gets you there, then go on down the list.

Claim: In order to generate a number with k 1s, you must take at least k trains. As proof, if you take a train and it doesn't cause a carry in your stop number, it sets 1 bit. If you take a train and it does cause a carry, the resulting number has at most 1 more set bit than it started with.

To get from x to 2^n is a bit trickier, but can be made simple by tracking the trains you take backwards.

Mapping s_i to s_{2^n-i} and reversing the train steps, any solution for getting from x to 2^n describes a solution for getting from 0 to 2^n-x. And any solution that is optimal for the forward one is optimal for the backward one, and vice versa.

Using the result for getting from 0 to y, we then get that the optimal route from a to b where b highest bit set is 2^n and a does not have that bit set is #b-2^n + #2^n-a, where # means "the number of bits set in the binary representation". And in general, if a and b have a common prefix, simply drop that common prefix.

A local rule that generates the above number of steps is "take the fastest train in your current location that doesn't overshoot your destination".

For the part going from 2^n to 2^n+y we did that explicitly in our proof above. For the part going from x to 2^n this is trickier to see.

First, if the low order bit of x is set, obviously we have to take the first and only train we can take.

Second, imagine x has some collection of unset low-order bits, say m of them. If we played the train game going from x/2^m to 2^(n-m), then scaled the stop numbers by multiplying by 2^m we'd get a solution to going from x to 2^n.

And #(2^n-x)/2^m = #2^n - x. So this "scaled" solution is optimal.

From this, we are always taking the train corresponding to our low-order set bit in this optimal solution. This is the longest range train available, and it doesn't overshoot 2^n.

QED

First, ask if you can go backward. It sounds like you can't, but as presented here (which may not reflect the question as you received it), the problem never gives an explicit direction for any of these trains. (I see you've now edited your question to say you can't go backward.)

Assuming you can't go backward, the strategy is simple: always take the highest-numbered available train that doesn't overshoot your destination.

Suppose you're at stop s, and the highest-numbered train that stops at your current location and doesn't overshoot is train k. Traveling once on train k will take you to stop s + 2^(k-1). There is no faster way to get to that stop, and no way to skip that stop - no lower-numbered trains skip any of train k's stops, and no higher-numbered trains stop between train k's stops, so you can't get on a higher-numbered train before you get there. Thus, train k is your best immediate move.

With this strategy in mind, most of the remaining optimization is a matter of efficient bit twiddling tricks to compute the number of stops without explicitly figuring out every stop on the route.