How should I practice Dungeon Health?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs onsite interview problems in FastPrep.

Is Dungeon Health associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Dungeon Health

Learn this problem

● Hard

Goldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

A knight starts at the top-left cell of a nonempty rectangular dungeon dungeon and must reach the bottom-right princess cell. From any cell the knight may move only one step right or one step down.

Each cell contains an integer. A negative value is damage taken on entry. A nonnegative value is health recovered on entry. The knight's health is an integer that must stay at least 1 after entering every cell, including the start and the destination.

Return the minimum initial health that lets the knight reach the princess under an optimal path.

What the interview report shared

The Superday report asked dungeon health as a dynamic-programming problem.

Function

calculateMinimumHP(dungeon: int[][]) → int

Examples

Example 1

dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]return = 7

The path -2, then -3, then 3, then 1, then -5 needs initial health 7. Any cheaper start dies on this dungeon, and every other path needs at least as much.

Example 2

dungeon = [[0]]return = 1

The single cell is nonnegative, so the smallest legal starting health is 1.

Constraints

1 <= dungeon.length, dungeon[i].length <= 200.
dungeon is rectangular: every row has the same length.
-1000 <= dungeon[i][j] <= 1000.