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.