algorithm - 通过具有正成本和负成本的成本矩阵的最小成本路径

Question

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

我得到了一个成本矩阵 mxn。成本矩阵具有随机放置的正缓冲区和负成本。我从 [1,1] 开始，必须到 [m,n]。我从一个初始缓冲区 x 开始。在我的整个遍历过程中，我的缓冲区 x 永远不应该 <= 0。如果它变成 <= 0 那就是一条无效路径，即使最终状态是一个正缓冲区(把它想象成一个从一些初始健康开始的玩家，负成本扣除健康和积极的缓冲区增加健康)。我可以从什么开始到达 [m,n] 而中间没有 0 缓冲区的最小初始缓冲区是多少(例如，最小初始健康，以便玩家可以在不死亡的情况下完成路径)

Answer 1

假设 H[i, j] 是玩家从正方形 (i, j) 开始时所需的最低生命值。我们对 H[1, 1] 感兴趣，这是从起始方 block 开始所需的最低生命值。

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

踩到最后一个方 block 之前所需的健康很简单:如果该方 block 中的值为正，我们需要 1，否则我们至少需要比减去的更多:

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

其他简单的是矩阵的边:M[m, i] 和 M[j, n] 用于任意 i 和 j。如果当前值为负，我们必须增加所需的健康缓冲区，否则我们可以减少它(但绝不能超过 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))

就是这样!将其转换为代码很简单(假设给出了 M、m 和 n 并且 M 是基于 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];