Let's say that `H[i, j]`

is the minimum health the player
needs when starting from square `(i, j)`

. We are interested in
`H[1, 1]`

, which is the minimum health needed from the starting
square.

I assume that all values in the cost matrix `M`

are integers.
Therefore, the smallest positive health is 1.

The required health before stepping on the last square is easy: if the
value in that square is positive we need 1, otherwise we need at least more
than what gets subtracted:

```
H[m, n] = max(1 - M[m, n], 1)
```

The other easy ones are the edges of the matrix: `M[m, i]`

and `M[j, n]`

for arbitrary `i`

and `j`

.
If the current value is negative we have to increase the required health
buffer, otherwise we can decrease it (but never further than 1):

```
H[m, i] = max(H[m, i+1] - M[m, i], 1)
H[j, n] = max(H[j+1, n] - M[j, n], 1)
```

In the center of the matrix we have both choices (going right and down),
so we take the minimum of those alternatives:

```
H[i, j] = min(max(H[i, j+1] - M[i, j], 1),
max(H[i+1, j] - M[i, j], 1))
```

That's about it! Converting this to code is straightforward (assuming
`M`

, `m`

, and `n`

are given and
`M`

is 1-based):

```
int[] H = new int[m, n];
H[m, n] = max(1 - M[m, n], 1);
// remember to loop backwards
for (int i = m-1; i >= 1; i--)
H[m, i] = max(H[m, i+1] - M[m, i], 1);
for (int j = n-1; j >= 1; j--)
H[j, n] = max(H[j+1, n] - M[j, n], 1);
// again, loop backwards
for (int i = m-1; i >= 1; i--)
for (int j = n-1; j >= 1; j--)
H[i, j] = min(max(H[i, j+1] - M[i, j], 1),
max(H[i+1, j] - M[i, j], 1));
return H[1, 1];
```