# Grid Game Algorithm

You have to find the path with the maximum weight, from the top-left cell to the bottom-right cell. It could've been solved with a simple Dynamic Programming approach, if it were not for the special condition - you are allowed at most one move that can be either to the left or up. How do I now approach the problem with this special case?

Also, I'm looking for a time-efficient approach.

Thanks!

-
@YannisRizos I think that identifying Dynamic Programming as a potential strategy indicates an attempt to solve the problem independently. – dasblinkenlight Nov 6 '12 at 19:17
@dasblinkenlight Since you've already written a good answer, I'm ok with it. 7Aces for future reference, this isn't enough. You'll have to tell us exactly what have you tried. – Yannis Nov 6 '12 at 19:25

It is still doable with the special case, but you need to add a third logical dimension to your DP, indexed by a Boolean variable. This new dimension distinguishes between the scores before the special move (when the index is `false`) and the scores after the special move (when the index is `true`). The other two dimensions remain the grid's `rows` and `columns`.
When you compute the best score for a cell at `[r][c]`, you must compute two values:
1. A value where the third index is `false`. This result is computed based only on other values from the dimension where the index is `false`, looking at the cells to the left and up from `[r][c]`
2. A value where the third index is `true`. This result is computed based on values from both indexes: you consider the items to the left and up where the index is `true`, and also the items to the left, to the right, up, or down from `[r][c]`.
The second set of values (index == `true`) must be calculated after the entire set of the first items has been computed. In other words, you solve the problem with no special move, and then use the table for that solution to build an expanded table for the solution that allows special moves.