# Ac solution code

• Solutino1. Bottom-Up DP - Runtime = O(nm); Space = O(nm)

``````Iterate from last row to first row:
2-D table for the minimum DP.
h[i][j] is the minimum helth to enter (i, j)
h[0][0] is the anwser.
``````

JAVA Code:

``````public int calculateMinimumHP(int[][] A) {
int n = A.length, m = A[0].length;
int dp[][] = new int[n][m];// dp[i][j]: minimum hp to enter (i, j)

dp[n-1][m-1] = Math.max(-A[n-1][m-1], 0) + 1;// right-bottom node
for (int i = n - 2; i >= 0; i--) // last row
dp[i][m-1] = Math.max(1, dp[i+1][m-1] - A[i][m-1]);
for (int j = m - 2; j >= 0; j--) // last column
dp[n-1][j] = Math.max(1, dp[n-1][j+1] - A[n-1][j]);

for (int i = n - 2; i >= 0; i--) {// calculate dp table
for (int j = m - 2; j >= 0; j--) {
dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]);// right, down
dp[i][j] = Math.max(1, dp[i][j] - A[i][j]);
}
}
return dp[0][0];
}
``````

Solution2. Memorized DFS

Regular DFS without memorization will cause TLE error.

``````public int calculateMinimumHP(int[][] A) {
int maxDamages[][] = new int[A.length][A[0].length];// KEY optimization: Memorization for the previous results
for (int i = 0; i < A.length; i++) Arrays.fill(maxDamages[i], Integer.MAX_VALUE);

int maxDamage = DFS(A, 0, 0, maxDamages);
return Math.max(0, -maxDamage) + 1;
}

int DFS(int[][] A, int i, int j, int maxDamages[][]) {// Total damage for one path
if (i > A.length - 1 || j > A[0].length - 1) return Integer.MIN_VALUE;
if (maxDamages[i][j] != Integer.MAX_VALUE) return maxDamages[i][j];// **Return the memorized result, to avoid duplicated DFS

int maxDamage;
if (i == A.length - 1 && j == A[0].length - 1) {// Right-bottom node
maxDamage = A[i][j];
} else {
int right = DFS(A, i, j+1, maxDamages);
int down =  DFS(A, i+1, j, maxDamages);
maxDamage = Math.max(right, down) + A[i][j];// Choose the path with less damage: rightward, downward
}
maxDamages[i][j] = Math.min(0, maxDamage);
return maxDamages[i][j];
}``````

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