```
dp[i][j] : minimal hp needed if I want to go to position i, j from 0, 0
hp[i][j] : keep track of the hp state through the optimal path
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int n = dungeon.size();
int m = dungeon[0].size();
int dp[n][m], hp[n][m];
dp[0][0] = dungeon[0][0] > 0 ? 1 : -1 * dungeon[0][0] + 1;
hp[0][0] = dp[0][0] + dungeon[0][0];
for(int i = 1; i < n; i++) {
int t = hp[i - 1][0] + dungeon[i][0];
dp[i][0] = dp[i - 1][0] + (t > 0 ? 0 : -1 * t + 1);
hp[i][0] = t <= 0 ? 1 : t;
}
for(int i = 1; i < m; i++) {
int t = hp[0][i - 1] + dungeon[0][i];
dp[0][i] = dp[0][i - 1] + (t > 0 ? 0 : -1 * t + 1);
hp[0][i] = t <= 0 ? 1 : t;
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
int l = hp[i][j - 1] + dungeon[i][j], u = hp[i - 1][j] + dungeon[i][j];
int ll = dp[i][j - 1] + (l > 0 ? 0 : -1 * l + 1);
int uu = dp[i - 1][j] + (u > 0 ? 0 : -1 * u + 1);
dp[i][j] = ll;
hp[i][j] = l <= 0 ? 1 : l;
if(uu < ll || (uu == ll && u > l)) {
dp[i][j] = uu;
hp[i][j] = u <= 0 ? 1 : u;
}
}
}
return dp[n - 1][m - 1];
}
```