LeetCode 174 Dungeon Game

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-19 13:11:01
    编辑于：2022-02-19 15:06:25
    浏览量：734

概述

https://leetcode.com/problems/dungeon-game/

动态规划法（三维的状态定义）

第一次 TLE，忘记加 cache，之后加 cache，WA，是因为 h 改变了，忽视了这一点，导致更新了错的 h。纠正之后（加了 oldH）再次 TLE：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        vector<vector<unordered_map<int, int>>> dp(dungeon.size(), vector<unordered_map<int, int>>(dungeon[0].size()));
        return 1 + helper(dp, dungeon, 0, 0, 1);
    }
    
    int helper(vector<vector<unordered_map<int, int>>>& dp, vector<vector<int>>& dungeon, int i, int j, int h) {
        if (i == dungeon.size() || j == dungeon[0].size()) return INT_MAX;
        if (dp[i][j][h] != 0) return dp[i][j][h];
        int oldH = h;
        int extraHP = 0;
        if (dungeon[i][j] < 0) {
            h += dungeon[i][j];
            if (h <= 0) {
                extraHP = 1 - h;
                h = 1;
            }
        } else {
            h += dungeon[i][j];
        }
        
        int minFutureExtraHP = min(helper(dp, dungeon, i + 1, j, h), helper(dp, dungeon, i, j + 1, h));
        if (i == dungeon.size() - 1 && j == dungeon[0].size() - 1) minFutureExtraHP = 0;
        dp[i][j][oldH] = extraHP + minFutureExtraHP;
        return dp[i][j][oldH];
    }
};

两次 TLE 的 case 相同，看来我们加的 cache 不是很有效。

也难怪，dp cache 都三维了。

动态规划法（二维的状态定义）

我们能不能把上面的 h 这个维度去掉呢？

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        vector<vector<int>> dp(dungeon.size(), vector<int>(dungeon[0].size(), -1));
        return helper(dp, dungeon, 0, 0);
    }
    
    int helper(vector<vector<int>>& dp, vector<vector<int>>& dungeon, int i, int j) {
        if (i == dungeon.size() || j == dungeon[0].size()) return INT_MAX;
        if (dp[i][j] != -1) return dp[i][j];
        int initialHP = 1;
        int hp = 1;
        if (dungeon[i][j] < 0) {
            initialHP = -dungeon[i][j] + 1;
            hp = 1;
        } else {
            hp = dungeon[i][j] + 1;
        }
        
        int restHP = min(helper(dp, dungeon, i + 1, j), helper(dp, dungeon, i, j + 1));
        if (restHP == INT_MAX) restHP = 0;
        if (hp < restHP) {
            initialHP += restHP - hp;
        }
        dp[i][j] = initialHP;
        return initialHP;
    }
};

Links: leetcode-174-dungeon-game