# Dungeon Game

174. Dungeon Game

The demons had captured the princess 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 was initially positioned in **the top-left room** and must fight his way through `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 (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

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

Return *the knight's minimum initial health so that he can rescue the princess*.

**Note** that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

**Example 1:**

1 | Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] |

**Example 2:**

1 | Input: dungeon = [[0]] |

# Solution

这是一个典型的动态规划(DP)问题, 先规定几个变量:

1 | int minimumHP; //进入当前房间所需的初始生命值 |

显然有: minimum HP + currentRoomValue == minimum HP for next room

翻译: 进入当前房间所需的最小初始生命值 + 当前房间的魔法具有的加/减血 效果 = 进入下一个房间所需的最小初始生命值

因此有: **minimum HP = minimum HP for next room - currentRoomValue**

翻译: 进入当前房间所需的最小初始生命值 = 进入下一个房间所需的最小初始生命值 - 当前房间的魔法具有的加/减血 效果

这就是我们的循环不变式.

**Note:** the knight has an initial health point represented by a positive integer. So we must have: **minimum HP >= 1**.

建立DP数组`memo[][]`

, `memo[row][col]`

:= 进入坐标为`[row][col]`

的房间所需的最小初始生命值. `memo[0][0]`

即问题的解:

1 | public int calculateMinimumHP(int[][] dungeon) { |

`memo[row][col]`

的值依赖于`currentRoomValue`

和 `minimumHPForNextRoom`

.

已知`currentRoomValue == dungeon[row][col]`

, 接下来求`minimumHPForNextRoom`

.

由于规定了每一步只能往右或者往下走, "下一个"房间有多种情况, 需要分类讨论`minimumHPForNextRoom`

的值.

## Compute `minimumHPForNextRoom`

如果当前房间已经位于最右下角, 那么就没有下一个房间, 此时minimum HP for next room就等于1, 因为要保证从该房间离开时HP >= 1.

1 | // ... 计算minimumHPForNextRoom |

对于非最右下角的房间, 如果它位于最底端或者最右端, 那么下一步只有一种选择:

1 | if(row == m-1 && col == n-1) |

在上述情况之外, 下一步总是可以往右或者往下走, 所以进入下一个房间所需的最小初始生命值是 `min (memo[row+1][col], memo[row][col+1])`

. 即:

1 | if(row == m-1 && col == n-1) |

# Code

1 | /** |