Dungeon Game

Understand how to apply dynamic programming to calculate the minimum initial health a knight needs to navigate a dungeon grid filled with demons and magic orbs. This lesson helps you solve optimization problems by evaluating health impact at each step and ensures the knight safely reaches the princess without dying.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

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 $m × n$ , where each cell contains an integer value that affects the knight’s health.

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 contains a negative integer, it represents a demon that decreases the knight’s health.
If a cell contains zero, it is an empty room with no effect. ...