leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0174.cpp (477B)

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