Description
The knight has an initial health point of 1. What is the minimum initial health he needs to rescue the princess in the bottom-right corner?
Examples
Input:
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]Output:
7Explanation:
Initial health 7 is the minimum to survive.
Input:
dungeon = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
dungeon = [[0,-5,2],[-3,4,-1]]Output:
4Explanation:
The knight needs initial health of 4. The optimal path is right->right->down: Start with 4 health, cell [0,0] (value 0) keeps health at 4, cell [0,1] (value -5) drops health to -1, so at least 6 initial health is needed for this path. The globally optimal path requires starting with 4 health.
Constraints
- •
1 ≤ m, n ≤ 200 - •
-1000 ≤ dungeon[i][j] ≤ 1000