160. Dungeon Game

Hard · Dynamic Programming

A knight must traverse a dungeon from the top-left cell to the bottom-right cell, moving only right or down. Each cell contains a value that adds to or subtracts from the knight's health points (HP). The knight must maintain HP ≥ 1 at all times during the journey, including at the final cell. Given an m×n grid where each cell is an integer representing the HP change, determine the minimum positive starting HP required to reach the exit alive. Input is a 2D array of integers representing the dungeon grid. Return a single integer: the minimum starting HP needed.

Examples

Example 1
Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: Best path needs starting HP 7 to survive
Example 2
Input: [[0]]
Output: 1
Explanation: Cell is harmless; minimum positive HP is 1

Constraints