算法

(二分、dp) $O(nm * log\,end)$

本题采用二分+dp check的做法

• 二分是对于答案进行二分。
• check的时候我们要用dp进行，考虑到起点用mid的血量开始到终点是否够，最后比较得出答案

C++ 代码

class Solution {
public:
    bool canSurvive(int health, vector<vector<int>> &dungeon){
        int n = (int)dungeon.size(), m = (int)dungeon[0].size();
        vector<vector<int>> f(n,vector<int>(m,0));
        f[0][0] = dungeon[0][0] + health;
        if (f[0][0] <= 0) {
          return false;
        }

        for (int i = 1; i < n; i++) {
          f[i][0] = f[i - 1][0] == -1e9
                    ? -1e9
                    : f[i - 1][0] + dungeon[i][0];
          if (f[i][0] <= 0) {
            f[i][0] = -1e9;
          }
        }
        for (int i = 1; i < m; i++) {
          f[0][i] = f[0][i - 1] == -1e9
                    ? -1e9
                    : f[0][i - 1] + dungeon[0][i];
          if (f[0][i] <= 0) {
            f[0][i] = -1e9;
          }
        }

        for (int i = 1; i < n; i++) {
          for (int j = 1; j < m; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (f[i][j] == -1e9) {
              continue;
            }
            f[i][j] += dungeon[i][j];
            if (f[i][j] <= 0) {
              f[i][j] = -1e9;
            }
          }
        }
        return f[n - 1][m - 1] > 0;
    }

    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int start = 1, end = 1e9;
        while (start < end) {
          int mid = (end + start) / 2;
          if (canSurvive(mid, dungeon)) {
            end = mid;
          } else {
            start = mid + 1;
          }
        }
        return start;
    }
};