通过具有正、负成本矩阵的最小成本路径

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)

其他简单的方法是矩阵的边：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];