Solution: Dungeon Game
Understand how to apply dynamic programming techniques to solve the Dungeon Game problem by calculating the minimum initial health a knight needs to rescue the princess while navigating a 2D grid with health-affecting cells. This lesson guides you through constructing and using a DP table to ensure the knight’s health never drops to zero or below.
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 ...