Class Solution

LeetCode_problems/Dungeon Game/solution.cpp:20–45

// Time complexity : O(MN) i.e. the given matrix's dimensions.

class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>> &dungeon)
    {
        int r = dungeon.size();                    // row size
        int c = dungeon[0].size();                 // column size
        vector<vector<int>> dp(r, vector<int>(c)); // initializing the DP table with same size as given matrix
        // looping for filling the DP array starting from bottom right cell. the pattern is right to left ,then down to top
        for (int i = r - 1; i >= 0; --i)
        {
            for (int j = c - 1; j >= 0; --j)
            {
                if (i == r - 1 && j == c - 1)                                           //Bottom-Right cell (Princess Cell) (point 1.)
                    dp[i][j] = min(0, dungeon[i][j]);                                   // taking min so as to replace the positive value with 0
                else if (i == r - 1)                                                    //last row, (point 2)
                    dp[i][j] = min(0, dungeon[i][j] + dp[i][j + 1]);                    // taking min so as to replace the positive value with 0
                else if (j == c - 1)                                                    //last col, point (3)
                    dp[i][j] = min(0, dungeon[i][j] + dp[i + 1][j]);                    // taking min so as to replace the positive value with 0
                else                                                                    // any other cell (point 4)
                    dp[i][j] = min(0, dungeon[i][j] + max(dp[i][j + 1], dp[i + 1][j])); // taking min so as to replace the positive value with 0
            }
        }
        return abs(dp[0][0]) + 1; // Adding one because the knight can not start with value 0 as mentioned in point 5
    }
};