Recursion to DP Solution
The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

Function OPT(i, site):
    If i = 0, return 0
    If i &gt; 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
    If i &gt; 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)


If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

Function OPTm(i, site):
    If i = 0, return 0
    If (i, site) in Database, return Database(i, site)
    If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
    If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)
    Database(i, site) = answer
    return answer