minimum cost path through a cost matrix with positive and negative cost

Question

this is a variant of the minimum cost path dynamic programming problem that has me stumped.

I'm given a cost matrix mxn. The cost matrix has positive buffers and negative costs randomly placed. I start from [1,1] and have to go to [m,n]. I start with an initial buffer, x. Throughout my traversal, my buffer x should never be <= 0. If it becomes <= 0 thats an invalid path even if the end state is a positive buffer(think of it like a player starting with some initial health, the negative cost deducts health and the positive buffer adds health). What is the minimum initial buffer I can start with to make it to [m,n] without having a 0 buffer anywhere in between(as in, minimum initial health so that the player can finish the path without dying)

Answer 1

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];