Given an m x n grid representing a dungeon, compute the minimum initial health required for the knight to reach the princess. The knight can only move right or down, and health must never drop to 0 or below. This is a strong state-definition DP problem.
dungeon = grid of health gains/losses
minimum initial health needed
Example 1:
Input:
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output:
7
Explanation:
The knight needs at least 7 health to survive the path.
Example 2:
Input:
dungeon = [[0]]
Output:
1
Explanation:
Even with zero damage, the knight must start with at least 1 health.