具有正负成本的成本矩阵中的最小成本路径

Question

这是最小成本路径动态规划问题的一个变体，让我难倒了。

我得到了一个成本矩阵MXN。成本矩阵有随机放置的正缓冲区和负成本。我从[1,1]开始，必须到[m,n]。我从一个初始缓冲区x开始。在我的遍历过程中，我的缓冲区x永远不应该<=0。如果它变成<=0，那么即使结束状态是一个正缓冲区，也是一个无效的路径（把它想象成一个玩家从一些初始健康开始，负成本扣除健康，而正缓冲区增加健康）。什么是最小的初始缓冲区，我可以开始使它达到[m，n]，而没有0缓冲区之间的任何地方（例如，最小的初始生命值，以便玩家可以完成路径而不死亡）

Answer 1

假设h[i,j]是玩家从正方形开始(i,j)时所需的最小健康值。我们对h[1,1]感兴趣，这是从起始方块开始所需的最小健康状态。

我假设成本矩阵M中的所有值都是整数。因此，最小的正健康是1。

踩最后一个方块之前所需的健康值很容易：如果该方块中的值为正，我们需要1，否则我们至少需要比减去的值更多：

H[m, n] = max(1 - M[m, n], 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)

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

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