PreviousNext
Coding/Dynamic programming

Dungeon minimum starting health

Write codeHard30 minGoogle style

Your task

A knight enters the top-left cell of an m x n dungeon and must reach the princess in the bottom-right cell, moving only right or down. Each cell adds its integer value to the knight's health (negative cells are damage, positive cells are potions). If the knight's health ever drops to 0 or below, the knight dies. Return the minimum positive starting health that guarantees the knight reaches the princess alive. Grid dimensions are at least 1x1.

Examples

calculate_minimum_hp(dungeon: list[list[int]]) -> int
Example 1
Inputcalculate_minimum_hp([[-2, -3, 3], [-5, -10, 1], [10, 30, -5]])
Output7