Accenture | Online | Person coins

Accenture | Online | Person coins

Travelling down a grid
A person is trying to reach the bottom of a n x m grid. The person starts with 1000 coins. Person wants to find a away that will leave the largest amount of coins in person pocket.

• Person can start from any cell in the first row
• Each step, person can only go down or diagonally (down left and down right)
• The journey is finished when last row of the grid is reached
  Example:
  Array[][]=[[10,20,30,40],
  [60,50,20,80],
  [20,20,20,20],
  [60,50,20,80]]
  The best path: 1000 - Array[0][1] – Array[1][2] – Array[2][2] – Array[3][2] = 920.

Any ideas how to do it?
I've a problem with that queston. I've tried to use a recursion, but I couldn't make it.