地牢遊戲解決方案的解釋

Question

地牢遊戲描述爲：

惡魔抓獲了公主（P），並在地牢的右下角囚禁她 。 T 他的地牢由二維網格佈置的M×N房間組成。 我們英勇的騎士（K）最初被定位在左上角的房間 中，並且必須通過地牢戰鬥以拯救公主。

騎士具有以正整數表示的初始健康點。 如果他的健康點在任何時候降至0或以下，他立即死亡。

部分房間由惡魔守衛， 因此騎士在進入這些房間時失去健康（負整數）;其他房間要麼是空的（0），要麼包含增加騎士身體（正整數）的魔法球。

爲了儘快到達公主， 騎士決定只在每一步中向右或向下移動。

編寫一個函數來確定騎士的最低初始健康狀況 以便他能夠拯救公主。

例如，考慮到下面的地牢， 的最初生命值，如果騎士遵循最佳路徑RIGHT-> RIGHT-> DOWN-> DOWN，則該騎士必須至少爲7。

備註：

騎士的健康沒有上限。 任何房間都可能包含威脅或通電，即使是騎士進入的第一個房間 和公主被監禁的右下角房間。

例子：

dungeon = [[-2, -3, 4], 
      [-6, -15, 0], 
      [10, 25, -6]] 

答：8

代碼的解決方案是：

def dungeonGame(dungeon): 
    dp = [float("inf") for _ in dungeon[0]] 
    dp[-1] = 1 

    for i in reversed(range(len(dungeon))): 
     dp[-1] = max(dp[-1] - dungeon[i][-1], 1) 
     for j in reversed(range(len(dungeon[i]) - 1)): 
      min_HP_on_exit = min(dp[j], dp[j + 1]) 
      dp[j] = max(min_HP_on_exit - dungeon[i][j], 1) 

    return dp[0] 

有人可以解釋如何解決上述的工作？爲什麼僅使用所提供的示例的dp len 3？是因爲只需要3個步驟，不包括開始和結束房間？爲什麼它在相鄰的DP上獲得最小值，然後是最大值？另外，自從地牢[i] [j]以來，最後一列似乎沒有被考慮到，其中j僅上升到1（以給定示例矩陣）。我知道解決方案寫得很好，只是想了解它如何考慮所有的路徑。

Answer 1

該算法從右下角開始，從左到右，沿着每個步驟找到最佳分數。我建議你用筆和紙執行算法，一路寫下i，j和dp的當前值。這應該真的清除了一切。

（開始）：不，我沒有Ĵ然而，DP = [INF INF 1]

爲了贏得到達右下角後，您將需要至少1 HP。

（進入第一個循環後）：i = 2，dp = [inf inf 7]。

您需要7點生命才能在右下方正方形本身的-6點生存。

（進入內循環後）：I = 2，J = 1，DP = [INF 1 7]

如果你在底部中心廣場，最低限度1健康足以生存該方格的+25，並且到達需要至少7的相鄰方格。等等。

這是在向右（存儲在中間結果的下一個元素，dp[j + 1]）或下，dp[j]之間選擇的關鍵線。

min_HP_on_exit = min(dp[j], dp[j + 1]) 

只有三個要素的中間結果，因爲與運動規則（僅移動向右和向下）和對角線爲3地牢，只有最多3個地方，你可能是之後的任何移動次數。

每次解算器向上移動一行，最後一列的照顧作爲特殊情況在這裏：

dp[-1] = max(dp[-1] - dungeon[i][-1], 1) 

爲什麼？那麼，它與其他專欄不同，因爲你不能向右移動，只能向下移動。