Dungeon Game

Explore how to apply dynamic programming to solve the Dungeon Game problem in C++. Understand how to calculate the minimum health needed for the knight to safely travel through a grid-based dungeon with demons and magic orbs, ensuring the knight's survival at every step.

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. ...