Java DP Solution O(MN)


  • 0
    N
    public int calculateMinimumHP(int[][] dungeon) {
            int col = dungeon.length, row = dungeon[0].length;
            int[][] dp = new int[col][row];
            int sum;
            for (int i = col-1; i >= 0; --i) {
                for (int j = row-1; j >= 0; --j) {
                    sum = dungeon[i][j];
                    if (i < col-1 && j < row-1) {
                        if (dp[i+1][j] > dp[i][j+1]) {
                            sum += dp[i+1][j];
                        } else {
                            sum += dp[i][j+1];
                        }
                    } else if (i < col-1) {
                        sum += dp[i+1][j];
                    } else if (j < row-1) {
                        sum += dp[i][j+1];
                    }
                    dp[i][j] = sum > 0 ? 0 : sum;
                }
            }
        return 1-dp[0][0];
        }
    

Log in to reply
 

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