# Share DP Solution from "Bottom right corner" to "Upper left corner"

• Let A[i][j] denotes the least HP when the knight reached dungeon[i][j].

1. Calculate the least HP at the bottom right corner, dungeon[row-1][col-1]:

``````If dungeon[row-1][col-1] > 0, A[i][j] = 1;    // the last room contains supplies
else A[i][j] = 1 - dungeon[row-1][col-1];     // the last room is guarded by demons
``````
1. Calculate the least HP when the knight in the last column bottom-up;
2. Calculate the least HP when the knight in the last row from right to left;
3. Calculate the least HP when the knight in other areas from bottom-right to upper-left.

``````int calculateMinimumHP(vector<vector<int> > &dungeon) {
int row = dungeon.size();
int col = dungeon[0].size();
int A[row][col];

// 1. when the knight reached the bottom right corner
A[row-1][col-1] = (dungeon[row-1][col-1] > 0) ? 1 : (1 - dungeon[row-1][col-1]);

// 2. in the last column, bottom-up;
for(int i = row - 2; i >= 0; --i) {
int aboveValue = A[i+1][col-1] - dungeon[i][col-1];
A[i][col-1]  = aboveValue > 0 ? aboveValue : 1;
}

// 3. in the last row, from right to left
for(int j = col - 2; j >= 0; --j) {
int leftValue = A[row-1][j+1] - dungeon[row-1][j];
A[row-1][j]  = leftValue > 0 ? leftValue : 1;
}

// 4. in other areas, from bottom-right to upper-left
for(int i = row - 2; i >=0; --i) {
for(int j = col - 2; j >= 0; --j) {
int rightValue = (A[i][j+1]-dungeon[i][j] > 0) ? A[i][j+1]-dungeon[i][j] : 1;
int belowValue = (A[i+1][j]-dungeon[i][j] > 0) ? A[i+1][j]-dungeon[i][j] : 1;
A[i][j] = min(rightValue, belowValue);
}
}
return A[0][0];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.