# I want to fill dp table from top left to bottom right, but get WA on test31, here is my code

• ``````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];
}``````

For the following input,

``````0,0,0,
-1,0,0,
2,0,-2,
``````

The expected answer is `2` but your code returned `3`.

• Yes. A new test case is added. A local minimum cannot guarantee a global minimum dp.

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