We review another example of moving on a checkerboard . We are given an n by n checkerboard it's valid to move ftom any of the boxes on the bottom to goto any of the boxes in the top board.  A move can only be made to a square on the top left, directly above and a top right as long as they are within the square checkout  each move results in a positive or negative amount of money . We have to find the optimal set of moves that maximizes profit.
We apply dynamic programming by defining the opt optimal substructure.
The current position i,j can be moved to from one of three positions in the row below. Because we make an opt choice in this move, the previous set of Moves upto and inclusive of the previous position is also optimal.
Hence we define as recurrence relationship as

Next move = p [(i-1,j-1), (i,j)] + d (i-1,j-1)
                     = p [(i-1,j), (i,j)] +d (i-1,j)
                      =p[i-1, j+1 , (i,j)] + d (i-1, j+1)
And repeat for n steps.
The bottom up method would be like this:
let d[1..n, 1..n] and s[1 .. n-1, 2..n] be new tables for cost and index of optimal

for i = 1 to n

    d[i,i] = - infinity

for l = 2 to n // chain length

     for i = 2 to n-l+1

           j = i+l-1

           d[i,j] = - infinity

           q = max ( p [(i-1,j-1), (i,j)] + d (i-1,j-1)

                     , p [(i-1,j), (i,j)] +d (i-1,j)

                      , p[i-1, j+1 , (i,j)] + d (i-1, j+1))

                 if q > d[i,j]

                     d[i,j] = q

                     s[i,j] = k

return d and s


The top down strategy using recursion is as follows:

RecursiveStepping (i, j, d)

   If I == n-1
         Return d(i,j)
   Q = max (p [(i-1,j-1), (i,j)]+ RecursiveStepping (i-1,j-1,d)

                     , p [(i-1,j), (i,j)] +RecursiveStepping(i-1,j,d)

                      , p[i-1, j+1 , (i,j)] + RecursiveStepping (i-1, j+1, d))
    If q > d (i,j)
      D (i,j) = k
   Return d(i,j)