Solution: Dungeon Game
Explore how to apply dynamic programming to calculate the minimum initial health a knight needs to safely navigate a dungeon grid filled with health-affecting cells. This lesson teaches you to work backward from the destination to determine the health required at each step, ensuring the knight never dies before reaching the princess, while practicing optimization techniques.
We'll cover the following...
Statement
A group of demons has captured a princess and locked her in the bottom-right corner of a dungeon. The dungeon is represented as a 2D grid of size
The knight, starting in the top-left corner of the grid, must travel through the dungeon to rescue the princess.
He can move only to the right or downward at each step.
If a cell ...