Why the "binary search" tag?


  • 4
    C

    As we all know the typical solution is via DP, which is also the given solution. I can't think of how it can relate to binary search, any ideas?


  • 14
    S

    Because it is also possible to use binary search on HP for this particular problem. The idea is: for the middle value of the possible range of HP, we use DP to check if this middle value is too high or too low, and then repeat this process and throw half of the HP values that are impossible. The draw back of this problem is that it takes O(log(INT_MAX)MN), and only applies to integer HP values.


  • 0
    C

    I see now, it's pretty straightforward because this time DP is from top left.


  • 0
    W

    how to know one HP value is higher or lower than needed?


  • 1
    S

    Let's say we first try minHP=Integer.MAX_VALUE, and use DP to check whether the knight can save the princess. If the answer is yes, then we try another minHP=Integer.MAX_VALUE/2, and if again the knight can save the princess, the last value we tried (Integer.MAX_VALUE) must be larger than needed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.