[LeetCode] 174. Dungeon Game

轉自LeetCode

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight's minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

 

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

 

Constraints:

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

Solution

62. Unique Paths 的衍生題，解題方式也是一樣要用 DP

這題難的地方在於，是要求最小起始值，過程當中又有正值和負值

條件變得很複雜

這時候，看一下勝利條件，是到達終點的時候，生命值最少必須是 1

題目是要找最小的起始值，也就是到達終點，生命值剛好是 1 的時候

那個就是要找的最小起始值，所以，終點的值是可以確定的

如果終點的所需生命是正值，其實用 1 就可以了

如果終點的所需生命是負值，那終點的值就是 1 - dungeon[m][n]

因此，改從終點往起始點走，只能向上向左

過程當中，記錄進到每個 cell 所需的最小生命值

dp[r][c] = max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c])

min(dp[r+1][c], dp[r][c+1]) 很好理解，因為是要求最小生命值，選下方或右方比較小的值

min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]，當 dungeon[r][c] 是負值的時候，必須加上，dungeon[r][c] 才能確保不會死掉；當 dungeon[r][c] 是正值的時候，減掉 dungeon[r][c] 也沒關係，因為進到房間後，就會加上 dungeon[r][c] 了

max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c])，因為是要求活著的路線，所以如果生命值小於 1 的時候，卡在 1 這個值

code如下

kotlin