This is a sample dynamic programming. First you have to solve the problem for the n^th and (n-1)^th column and this is the subproblem. You should memorize the result and then solve it for (n-1)^th and (n-2)^th columns. In this way you should solve the total problem.

Remember about input size. It does not fit in 32-bit integer and can be negative. One best way is to use long long.

I have found a great help to solve this problem on the board.

Note: Most of the DP have a recursive solution. This problem also may have that. But I solve this without any recurrence. I use another 2D array to find the path.