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


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

  • 2

    Please resubmit your code again, you should get Wrong Answer for a smaller test case.

    For the following input,

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

    The expected answer is 2 but your code returned 3.


  • 0
    S

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


Log in to reply
 

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