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

Solution: Dungeon Game

Explore how to use dynamic programming to solve the Dungeon Game problem by determining the minimal health a knight must have to travel safely from the start to the princess. Understand how to work backward through a grid to manage health points, accounting for both health gains and losses, ensuring survival 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 ...