题目地址：

https://www.lintcode.com/problem/dungeon-game/description

给定一个二维矩阵$A$，一个骑士第一步会走到$(0,0)$的位置，之后每一步可以向右或者向下走一步，每走到$(i,j)$这个位置上，他的血量就会变化$A[i][j]$这么多（意思是，如果$A[i][j]$为正，他的血量就会增加；如果$A[i][j]$为负，他的血量就会减少；为$0$则不变）。他需要走到最右下角的位置，并且路径上不能有任何时刻血量是小于等于$0$的。问他初始的时候至少要多少血量。

思路是动态规划。设$f[i][j]$为走到$(i,j)$这个格子之前，最少要保有的血量。如果$(i,j)$恰好是右下角，那么显然有$f[i][j]=\max \{1,1-A[i][j]\}$，也就是如果$A[i][j]\le 0$，那么要保证他消耗了若干血量之后的血量仍然大于$0$，此外他走到之前一步的格子上的时候至少也要有$1$的血量。如果$(i,j)$不是右下角，则有$$f[i][j]=\max \{1,\min \{f[i+1][j],f[i][j+1]\}-A[i][j]\}$$显然这个血量应该满足$f[i][j]+A[i][j]\ge \min \{f[i+1][j],f[i][j+1]\}$，这里的min指的是我们挑需要血量更少的一条路去走；同时，还需要保持$f[i][j]\ge 1$。代码如下：

public class Solution { /** * @param dungeon: a 2D array * @return: return a integer */ public int calculateMinimumHP(int[][] dungeon) { // write your code here 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 { int min = Integer.MAX_VALUE; // 如果向下走，算一下需要的血量 if (i + 1 < m) { min = Math.min(min, dp[i + 1][j] - dungeon[i][j]); } // 如果向右走，算一下需要的血量 if (j + 1 < n) { min = Math.min(min, dp[i][j + 1] - dungeon[i][j]); } // 血量不能小于等于0 dp[i][j] = Math.max(1, min); } } } return dp[0][0]; } }

时空复杂度$O(mn)$。