> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/174-dungeongame.md).

# 174     Dungeon Game

## 174.[ Dungeon Game](https://leetcode.com/problems/dungeon-game/description/)

## 1. Question

The demons had captured the princess (**P**) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (**K**) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (*negative\_integers) upon entering these rooms; other rooms are either empty (\_0's*) or contain magic orbs that increase the knight's health (\_positive\_integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

**Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.**

For example, given the dungeon below, the initial health of the knight must be at least**7**if he follows the optimal path`RIGHT-> RIGHT -> DOWN -> DOWN`.

| -2(K) |  -3 |   3   |
| :---: | :-: | :---: |
|   -5  | -10 |   1   |
|   10  |  30 | -5(P) |

## 2. Implementation

**(1) DP**

思路: 这题和Unique Path的思路类似，不同在于现在问你在起始点的初始值最少可以是多少, 所以写法是从右上角到左上角，状态转移有4种情况:

(1) 当骑士在右下角时候，需要的血量至少是1，如果dungeon\[m - 1]\[n - 1]是负数的话，则需要 1 - dungeon\[m - 1]\[n - 1]，我们取两者中较大值，所以状态转移方程 dp\[i]\[j] = Math.max(dp\[i]\[j], 1 - dungeon\[i]\[j])

(2) 当骑士在 m - 1行时，dp\[i]\[j]的状态只取决于dp\[i]\[j + 1], 状态转移方程式dp\[i]\[j] = Math.max(1, dp\[i]\[j + 1] - dungeon\[i]\[j])

(3) 同理，当骑士在n - 1列时，dp\[i]\[j] = Math.max(1, dp\[i + 1]\[j] - dungeon\[i]\[j])

(4) 当在骑士在其他行列时，dp\[i]\[j]的状态取决于dp\[i + 1]\[j]和dp\[i]\[j + 1]之间的较小值, dp\[i]\[j] = Math.max(1, Math.min(dp\[i + 1]\[j], dp\[i]\[j + 1]) - dungeon\[i]\[j])

```java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0) {
            return 0;
        }

        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m][n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                }
                else if (i == m - 1) {
                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                }
                else if (j == n - 1) {
                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
                }
                else {
                    dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(mn), 空间复杂度O(mn)