Solution: Dungeon Game
Explore how to solve the Dungeon Game challenge by applying dynamic programming. Understand how to compute the minimum initial health for a knight navigating a grid with health effects, ensuring survival while moving toward the princess. This lesson teaches backward DP computation, optimizing health points by evaluating subsequent cell requirements and guarantees the path's safety.
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 ...