Dungeon Game
Hard · Dynamic Programming · about 30 minutes
Asked at Google, Amazon, Microsoft, Meta, Uber.
A knight starts at the top-left of an m × n dungeon and must reach the princess at the bottom-right, moving only right or down. Each cell changes his health by its value (negative = damage). His health must stay at least 1 at all times. Return the minimum initial health needed.