Solution: Dungeon Game
Understand how to apply dynamic programming to solve the Dungeon Game challenge by calculating the minimum initial health a knight needs to survive through a grid filled with health modifiers. This lesson guides you through backward computation, using a dp table to ensure the knight's health never drops to zero or below while reaching the princess.
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 ...