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

Solution: Dungeon Game

Understand how to apply dynamic programming to determine the minimum initial health needed for a knight to survive a dungeon grid. This lesson guides you through calculating health requirements backwards from the goal, ensuring survival by keeping health above zero as the knight moves right or down in pursuit of the princess.

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