How should I practice Dungeon Game?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tekion phone screen problems in FastPrep.

Is Dungeon Game associated with Tekion?

FastPrep tags this as a Tekion phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Dungeon Game

Learn this problem

● Hard

TekionFULLTIMEPHONE SCREEN

Problem statement

A knight starts at the top-left cell of a nonempty rectangular matrix dungeon and must reach the bottom-right 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, while 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 destination.

Return the minimum initial health that lets the knight reach the destination by choosing an optimal path.

Function

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

Examples

Example 1

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

The path -2, -3, 3, 1, -5 is survivable with initial health 7. No smaller initial value can survive an optimal route.

Example 2

dungeon = [[0]]return = 1

The only cell causes no damage, but health must remain positive, so the minimum initial health is 1.

Constraints

1 <= dungeon.length, dungeon[i].length <= 200
dungeon is rectangular.
-1000 <= dungeon[i][j] <= 1000