We model the problem as a shortest path problem in a graph in which the state is an ordered pair ~(square, jumplen)~, where ~square~ is the square at which Nikola is located and ~jumplen~ is the length of the preceding jump.

From state ~(square, jumplen)~ Nikola can move to state ~(square-jumplen, jumplen)~ moving backwards, or to state ~(square+jumplen+1, jumplen+1)~ moving forwards, assuming these jumps don't move him out of the playing area.

Notice that the graph is acyclic (meaning that there is no way to visit a state twice while traversing the graph), because forward jumps increase the ~jumplen~ parameter. Because of this, the length of the shortest path can be calculated with dynamic programming.

Let the function ~opt(square, jumplen)~ represent the smallest cost for Nikola to get from square ~square~ to square ~N~, if the preceding jump was of length ~jumplen~.

Here's how to calculate the value of the function:

• For ~square < 1~ or ~square > N~, ~opt(square, jumplen) = \infty~;
• For ~square = N~, ~opt(square, jumplen) = fee[N]~;
• Otherwise, $$\displaystyle opt(square, jumplen) = fee[square]+\min\{opt(square-jumplen, jumplen), opt(square+jumplen+1, jumplen+1)\}$$

The solution is then ~opt(2, 1)~.