Leetcode 174 Dungeon games (June 23, 2022)

Some demons caught the princess （P） And shut her in the lower right corner of the underground city . The underground city is made up of  M x N Two dimensional mesh of rooms . Our valiant Knight （K） Originally placed in the room in the upper left corner , He had to go through the dungeon and save the princess by fighting demons .

The knight's initial health points are a positive integer . If his health points drop to 0 Or below , He will die immediately .

Some rooms are guarded by demons , So Knights lose health points when they enter these rooms （ If the value in the room is a negative integer , The knight will lose health points ）; The other rooms are either empty （ The value in the room is 0）, Or it contains magic balls that increase the health points of knights （ If the value in the room is a positive integer , The knight will increase health points ）.

To get to the princess as soon as possible , The knight decided to move only one step to the right or down at a time .

Write a function to calculate the minimum initial health points required to ensure that the knight can save the princess .

for example , Consider the underground city of the following layout , If the knight follows the best path Right -> Right -> Next -> Next , The initial health points of the knight are at least 7.

-2 (K) -3 3
-5 -10 1
10 30 -5 §

explain :

There is no limit on knight health points .

Any room can be a threat to the knight's health points , It may also increase the knight's health points , Including the upper left room where the knight entered and the lower right room where the princess was imprisoned .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/dungeon-game
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .