通過成本矩陣的最小成本路徑，帶有正面和負面成本

Question

這是最小成本路徑動態規劃問題的一個變體，讓我難以置信。

我給出了一個成本矩陣mxn。成本矩陣具有隨機放置的正面緩衝和負面成本。我從[1,1]開始，必須去[m，n]。我從一個初始緩衝區x開始。在我遍歷的時候，我的緩衝區x不應該是< = 0.如果它變成< = 0即使結束狀態是一個正緩衝區，這也是一條無效路徑（想象它像一個以一些初始健康狀態開始的玩家，負成本減健康和積極的緩衝增加健康）。什麼是最初的初始緩衝區，我可以在沒有任何介於0之間的任何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];