## 174. Dungeon Game

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) |

**Note:**

- The knight's health has no upper bound.
- 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.

## Rust Solution

```
struct Solution;
impl Solution {
fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
let n = dungeon.len();
let m = dungeon[0].len();
let mut dp = vec![vec![0; m]; n];
for i in (0..n).rev() {
for j in (0..m).rev() {
if i + 1 < n && j + 1 < m {
dp[i][j] = 1.max(-dungeon[i][j] + dp[i + 1][j].min(dp[i][j + 1]));
continue;
}
if i + 1 < n {
dp[i][j] = 1.max(-dungeon[i][j] + dp[i + 1][j]);
continue;
}
if j + 1 < m {
dp[i][j] = 1.max(-dungeon[i][j] + dp[i][j + 1]);
continue;
}
dp[i][j] = 1.max(-dungeon[i][j] + 1);
}
}
dp[0][0]
}
}
#[test]
fn test() {
let dungeon = vec_vec_i32![[-2, -3, 3], [-5, -10, 1], [10, 30, -5]];
let res = 7;
assert_eq!(Solution::calculate_minimum_hp(dungeon), res);
}
```

Having problems with this solution? Click here to submit an issue on github.