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? Return the result as an integer.
Examples
Input:
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]Output:
7Explanation:
Path: right->right->down->down. Costs: -2,-3,3,1,-5. Start with 7, survive all rooms, end with 1 HP.
Input:
dungeon = [[1]]Output:
1Explanation:
Single cell with +1 health bonus. Knight needs minimum 1 HP to enter; gains 1 HP inside.
Input:
dungeon = [[0,-5,2],[-3,4,-1]]Output:
4Explanation:
Best path: down->right->right. Costs: 0,-3,4,-1. Start with 4 HP, lowest point is 1 HP. Survives.
Constraints
- •
1 ≤ m, n ≤ 200 - •
-1000 ≤ dungeon[i][j] ≤ 1000