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.
1def calculateMinimumHP(dungeon):
2 m, n = len(dungeon), len(dungeon[0])
3 dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
4 dp[m][n - 1] = dp[m - 1][n] = 1
5 for i in range(m - 1, -1, -1):
6 for j in range(n - 1, -1, -1):
7 min_health_on_exit = min(dp[i + 1][j], dp[i][j + 1])
8 dp[i][j] = max(min_health_on_exit - dungeon[i][j], 1)
9 return dp[0][0]This solution initializes a DP table with values set to infinity for easier minimum comparisons, except for the 'virtual' edges that allow transitions. Starting from the bottom-right corner, it calculates the health required from the target cell back to the knight's starting point, adjusting the minimum health based on the room's value and ensuring it doesn't fall below 1.
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.