# My bottom-up O(n^2) Java Solution with detailed explanation

• I use another 2-D array to store intermediate result. If you don't care modification of original array, you can replace all "result" as "dungeon". So O(1) space can be achieved.

Then use bottom-up strategy to compute the minimum initial health for each cell from bottom-right direction.

I use the current cell minus previous path's health requirement to compute reversed health requirement for each cell.

I use this line to update required health for each cell:

``````        result[i][j] = result[i][j] > 0 ? 0 : -result[i][j];
``````

The whole code:

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int[][] result = new int[dungeon.length][dungeon[0].length];

for (int i = dungeon.length - 1; i >= 0; i--) {
int[] row = dungeon[i];
for (int j = row.length - 1; j >= 0; j--) {
boolean rowEnd = i == dungeon.length - 1;
boolean columnEnd = j == row.length - 1;
if (rowEnd && columnEnd) {
result[i][j] = dungeon[i][j];
} else if (!rowEnd && !columnEnd) {
result[i][j] = dungeon[i][j] - Math.min(result[i + 1][j], result[i][j + 1]);
} else {
result[i][j] = dungeon[i][j] - result[i + (rowEnd ? 0 : 1)][j + (columnEnd ? 0 : 1)];
}
result[i][j] = result[i][j] > 0 ? 0 : -result[i][j];
}
}
return result[0][0] + 1;
}
}``````

• I have the same similar solution with you. Furthermore, you can just use one dimensional array result[colNumber] to update the result.

• Yes, I use 2-D array just make the logic looks clear. I have another post to share O(1) space solution by change original values.

• can you write it also top-down, for me always top down is much easier. I wrote the top down DP, but it does not pass the limit for me

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