#174

Dungeon Game

master · 1670 · lc hard +32 · verified · 40.9% accepted · 6,239 likes · top 21%

Description

A princess is held in the bottom-right cell of an m x n dungeon grid. A knight starts in the top-left cell and may move only right or down.

The knight dies immediately if health drops to 0 or below. Cells with negative values drain health (demons), zero means empty, and positive values restore health (magic orbs).

Return the minimum initial health the knight needs to survive and rescue the princess.

Note: any cell — including the starting cell and the goal cell — may contain any type of encounter.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

Output: 7

Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]

Output: 1

Code

1

2

3

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int: