Problem Link – http://www.iarcs.org.in/inoi/2009/zco2009/zco2009-1a.php
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!
2
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:
- A value where the third index is
false. This result is computed based only on other values from the dimension where the index isfalse, looking at the cells to the left and up from[r][c] - 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 istrue, 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.
0