【Leetcode】174. 地牢游戏（Dungeon Game）

【Leetcode】174. 地牢游戏（Dungeon Game）

Leetcode - 174 Dungeon Game (Hard)

题目描述：给定一个矩阵，每个位置有正数加血，负数减血，骑士要从左上角走到右下角，只能向下或向右移动，骑士血量小于等于 0 就死亡，求骑士达到右下角需要的最小初始血量。

解题思路：从终点向起点逆推，定义 dp[i][j] 表示 (i, j) 为起点时需要的初始血量，才能从 (1,j) 走到终点。应该取走下面和走右边的最小值，即 dp[i][j] = min(down, right)，计算 down 和 right 的值，在每个点，最低的血量值至少为 1，每一步走的时候应该保证使得 down 或者 right 的值最大，即 max(1, dp[i + 1][j] - dungeon[i][j])。

public int calculateMinimumHP(int[][] dungeon) {int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m][n]