174. Dungeon Game

發表於 | 分類於

problem

solution

逆向的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m= dungeon[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        dp[n-1][m-1] = max(1, 1-dungeon[n-1][m-1]);
        for(int i=n-2;i>-1;--i) dp[i][m-1] = max(1, dp[i+1][m-1] - dungeon[i][m-1]);
        for(int j = m-2;j>-1 ;j--) dp[n-1][j] = max(1, dp[n-1][j+1] - dungeon[n-1][j]);
        
        for(int i=n-2;i>-1;i--){
            for(int j=m-2;j>-1;j--){
                dp[i][j] = min(
                    max(1,dp[i+1][j] - dungeon[i][j]),
                    max(1, dp[i][j+1] - dungeon[i][j])
                        );
            }
        }
        
        
        return dp[0][0];
        
    }
};

analysis

  • time complexity O(nm)
  • space complexity O(nm)