437. The Least Health to Cross

Each cell of a grid changes your health by its value, which may be negative. You enter at the top-left, leave at the bottom-right, and may move only RIGHT or DOWN. Your health is applied on entering every cell, including the first and the last, and must be at least 1 at ALL times.

Print the least health you can start with.

The natural instinct is to fill forwards from the top-left, and it does not work. That is the lesson of the problem rather than an obstacle to get past.

Filling forwards, the value at a cell would have to be something like "the best health reachable here", and that is not enough to continue: a route arriving with lots of health may have needed a huge starting amount, while a route arriving weaker may have been cheap. Two quantities compete and neither dominates, so no single forward value decides the future.

Fill BACKWARDS instead, and the state becomes well defined:

need[i][j] = the least health required ON ENTERING (i, j) to survive to the end

need[last] = max(1, 1 - grid[last]) need[i][j] = max(1, min(need[i+1][j], need[i][j+1]) - grid[i][j])

Reading it aloud: you must arrive with enough to cover this cell and then meet whichever onward requirement is smaller. The outer max(1, ...) enforces the survival rule, because a generous cell cannot reduce the requirement below 1.

The answer is need[0][0]. Choosing the direction of the fill IS the solution here, which is why the problem sits in this sub-topic.

Constraints - `1 ≤ r, c ≤ 200` - `-1000 ≤ value ≤ 1000`