Sponsored
Sponsored
In this approach, we'll utilize dynamic programming to calculate the minimum health needed at each room starting from the bottom-right corner (princess's location) up to the top-left corner (knight's starting point). We'll create a 2D DP array where dp[i][j] represents the minimum health required to reach the princess when starting at cell (i, j). The main idea is to ensure that at any point, the knight never drops to zero or negative health.
The transition involves ensuring that the knight has enough health to move to one of the neighboring cells (right or down), covering the requirement to sustain the journey until the end.
Time Complexity: O(m * n), where m is the number of rows and n the number of columns.
Space Complexity: O(m * n), used by the dp table.
1function calculateMinimumHP(dungeon) {
2 const m = dungeon.length;
3 const n = dungeon[0].length;
4 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(Number.POSITIVE_INFINITY));
5 dp[m][n - 1] = dp[m - 1][n] = 1;
6 for (let i = m - 1; i >= 0; i--) {
7 for (let j = n - 1; j >= 0; j--) {
8 const minHealthOnExit = Math.min(dp[i + 1][j], dp[i][j + 1]);
9 dp[i][j] = Math.max(minHealthOnExit - dungeon[i][j], 1);
10 }
11 }
12 return dp[0][0];
13}This JavaScript solution creates a DP table with an extra row and column filled with positive infinity, except for the starting edges that aid in calculating from room to room from the princess's dungeon room back to the starting point. It recursively solves backward, employing the dungeon disputes.
In this approach, we use only a single row (or column) to store intermediate results, thereby reducing space complexity. The idea is based on modifying the DP solution to use space proportional to the minimum dimension of the matrix, proceeding row by row or column by column and updating the required health values as we simulate moving from the goal to the start in the minimal dimension.
Time Complexity: O(m * n), where m is the number of rows and n the number of columns.
Space Complexity: O(n), using reduced 1D list for the dp array.
1public int calculateMinimumHP(int[][] dungeon) {
2 In this Java solution, we've reduced space complexity by storing results for each row traversal in a single 1D array. The solution iterates backward through columns while updating each min-health leaving values, ultimately outputting the starting health for the knight accurately.