Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question
    
@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
3  
@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 Rizos Nov 6 '12 at 19:25
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Worked! Thanks a lot.. :D –  7Aces Nov 6 '12 at 18:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.