This is a sample dynamic
programming. First you have to solve the problem for the nth 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.
|