LeetCode - 解题笔记 - 174 - Dungeon Game

【官方题解参考】

正眼一看就会知道是动态规划，但是实际考虑的时候会发现一个问题：从左上到右下的方向的规划计算无法在后续确认的情况下完全确认。最优路径会随着后续的结果的选择而不断发生变化，无后效性不成立。

反过来看，实际上本体就是在求取初始值。因此如果将规划方向从左上变成右下，整个逻辑就通了……

最优子结构： d p [ i ] [ j ] dp[i][j] dp[i][j]，从终点（右下）到达当前点所需要的最小能量值

初始值： d p [ m − 1 ] [ n − 1 ] = max ⁡ ( 1 , 1 − d u n g e o n [ m − 1 ] [ n − 1 ] ) dp[m-1][n-1] = max (1, 1 - dungeon[m - 1][n-1]) dp[m−1][n−1]=max(1,1−dungeon[m−1][n−1])

初始条件：对应地，寻找正负关系

条件转移：找最小负担 d p [ i ] [ j ] = max ⁡ ( 1 , min ⁡ ( d p [ i + 1 ] [ j ] , d p [ i ] [ j + 1 ] ) − d u n g e o n [ i ] [ j ] ) dp[i][j]=max(1, min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]) dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])−dungeon[i][j])

• 时间复杂度： O ( M N ) O(MN) O(MN)，其中 M M M和 N N N分别为输入的长度信息，二维遍历
• 空间复杂度： O ( M N ) O(MN) O(MN)，其中 M M M和 N N N分别为输入的长度信息，dp中间结果存储

class Solution {
public:
    int calculateMinimumHP(vector>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        
        vector> dp = vector>(m, vector(n, 0));
        
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        
        int ans = dp[0][0];
        
        return ans;
    }
};

Solution 1的Python实现

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        
        dp = [[0] * n for _ in range(m)]
        
        dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
        for i in range(m - 2, -1, -1):
            dp[i][-1] = max(1, dp[i + 1][-1] - dungeon[i][-1])
        for j in range(n - 2, -1, -1):
            dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])
            
        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
                
        ans = dp[0][0]
        
        return ans