LeetCode 174 Dungeon Game

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

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/