Dungeon Game

Problem Statement

A knight starts at the top-left corner of a dungeon and must rescue a princess at the bottom-right corner. The knight can only move right or down.

Each cell contains an integer. A positive value gives health, a negative value removes health, and zero does nothing.

The knight dies if health drops to 0 or below at any point. Find the minimum initial health needed to reach the princess alive.

[
  [-2, -3,  3],
  [-5, -10, 1],
  [10, 30, -5]
]

The minimum initial health is 7. One optimal path is right, right, down, down. Along that path the knight visits values -2, -3, 3, 1, -5, so health evolves as 7 -> 5 -> 2 -> 5 -> 6 -> 1. The knight always stays above zero.