LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i][j] 表示进入 dungeon[i][j] 需要的最少健康点数。先构造终点的初始值，如果 dungeon[i][j] 为正数，则只需要 1 点，如果 dungeon[i][j] 为负数，则需要 1 - dungeon[i][j] 点。接着构造最后一行和最后一列的初始值，因为最后一行只能往右走，最后一列只能往下走。最后构造其它位置，其它位置可以选择往右或往下，选择两个方向中需要健康点数较小的即可

class Solution {
 public:
  int calculateMinimumHP(vector<vector<int>>& dungeon) {
    if (empty(dungeon) || empty(dungeon[0])) {
      return 1;
    }
    int m = size(dungeon);
    int n = size(dungeon[0]);
    vector<vector<int>> dp(m, vector<int>(n));
    dp.back().back() = max(1, 1 - dungeon.back().back());
    // 最后一列
    for (int i = m - 2; i >= 0; --i) {
      dp[i].back() = max(1, dp[i + 1].back() - dungeon[i].back());
    }
    // 最后一行
    for (int i = n - 2; i >= 0; --i) {
      dp.back()[i] = max(1, dp.back()[i + 1] - dungeon.back()[i]);
    }
    // 其它位置
    for (int i = m - 2; i >= 0; --i) {
      for (int j = n - 2; j >= 0; --j) {
        int tmp = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
        dp[i][j] = max(1, tmp);
      }
    }
    return dp[0][0];
  }
};