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

Solution: Dungeon Game

Explore how dynamic programming is applied to solve the Dungeon Game problem by calculating the minimum initial health needed for the knight to survive from the top-left to the bottom-right cell. Understand the backward approach that evaluates each cell's health impact and ensures the knight's health never drops to zero or below throughout the journey.

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

  • If a cell contains a positive integer, it represents a magic orb that increases the knight’s health.

The knight begins his journey with an initial health point (HP) represented by a positive integer.
At any point during his adventure, if his health becomes zero or less, he dies immediately.

Your task is to determine the minimum initial health the knight must have to rescue the princess safely, ensuring that his health never drops to zero or below at any point in the journey.

Note: Both the starting cell and the princess’s cell may contain demons or magic orbs.

Constraints:

  • m==m == dungeon.length

  • n==n == dungeon[i].length

  • 1≤1 \leq ...