Dynamic Programming - Dungeon Game

A knight starts in top-left of a dungeon, must reach bottom-right to save the princess. Each cell adds or subtracts health. Find minimum initial health (at least 1) needed.

Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]] → Output: 7

Input: [[0]] → Output: 1

Work backwards from bottom-right. dp[i][j] = minimum health needed when entering cell (i,j). dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).

dp[m][n-1] = max(1, 1 - dungeon[m-1][n-1]).
For i from m-1 to 0, j from n-1 to 0 (excluding bottom-right):
need = min(right_need, down_need) - dungeon[i][j].
dp[i][j] = max(1, need).

class Solution { public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length, n = dungeon[0].length; int[][] dp = new int[m + 1][n + 1]; for (int[] row : dp) java.util.Arrays.fill(row, Integer.MAX_VALUE); dp[m][n-1] = dp[m-1][n] = 1; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int need = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]; dp[i][j] = Math.max(1, need); } } return dp[0][0]; } }

Time Complexity: O(M*N)
Space Complexity: O(M*N)