Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Dungeon Game

Explore a dynamic programming solution to the Dungeon Game problem that calculates the minimum initial health a knight needs to survive and rescue the princess. Understand how to work backward through the dungeon grid, evaluating health impacts and determining optimal paths with efficient time and space complexity.

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 m×nm × 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 ...