Dungeon Min Health Problem

Dungeon Min Health Problem — ExecCode Hard DSA Practice

Solve the Dungeon Min Health problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A knight starts at the top-left of a dungeon of integer rooms (negative = damage, positive = potion) and must reach the bottom-right moving only right or down. Health is always at least 1; if it would drop below 1 the knight dies. Compute the minimum initial health that still survives every room on some path. Return the minimum starting health (>= 1). You are given: dungeon — m×n integers Return integer starting HP. Even if every room is positive you still need 1 HP to enter.

Examples

Input {'dungeon': [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]}; Output 7. Input {'dungeon': [[0]]}; Output 1. Input {'dungeon': [[-5]]}; Output 6

Constraints

Health is checked after adding the room value You cannot go left or up

Practice Dungeon Min Health free on ExecCode. Browse DSA problems, topic map, and placement guides.