hardDynamic Programming 2DPure DSA~40 min
Minimum Health To Cross Grid
A migration job walks a grid from top-left to bottom-right, moving only right or down. Each cell adds or drains health (negative cells cost health). Find the smallest starting health so the job never drops to 0 or below anywhere along the way.
Problem
Given an m×n grid of integers, return the minimum positive starting health needed to travel from the top-left to the bottom-right, moving only right or down, keeping health ≥ 1 at every cell.
Input
An m×n integer grid (1 ≤ m, n ≤ 200, −1000 ≤ cell ≤ 1000).
Output
An integer: the minimum starting health (at least 1).
Constraints
- 1 ≤ m, n ≤ 200
- Cells may be negative (damage), positive (heal), or zero
- Health must stay ≥ 1 throughout, including the final cell
Examples
Example 1
Input
grid = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output
7
Starting with 7 health survives the worst path to the goal.
Example 2
Input
grid = [[0]]
Output
1
A single non-damaging cell needs the minimum 1 health.