Grid Game Algorithm
- by 7Aces
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!