动态规划算法帮我过“魔塔”

您现在仍然可以在手机上玩这个游戏：

相信这款游戏勾起了很多人的童年回忆。记得小时候，一个人玩游戏机，两三个人围在一起指指点点。这导致玩游戏的人体验很差，而左边和右边的人却异常高兴。

理口第174题是类似的问题。我简单描述一下：

输入存储整数的二维数组网格。如果grid[i][j]为0，说明这个格子里有血瓶，可以通过它增加对应的生命值； if grid[i][j]==0，则这是一个空网格，通过它不会发生任何事情；如果grid[i][j]为0，则说明该格子内有怪物，穿过它就会损失相应的生命值。

现在你是一名骑士，并将出现在最上方的角落。公主被困在右下角。您只能向右和向下移动。骑士成功营救公主的最低初始生命值是多少？

换句话说，就是问你至少需要多少初始生命值才能让骑士从左上角移动到右下角，并且任何时候生命值都必须大于0。

函数签名如下：

intcalculateMinimumHP(int[][]grid);例如，在问题给出的例子中，输入如下二维数组网格，用K代表骑士，P代表公主：

算法应该返回7，这意味着骑士的初始生命值至少为7才能成功营救公主，行进路径如图中箭头所示。

在上一篇文章Minimum Path Sum中，我写了一个类似的问题，问你从左上角到右下角的最小路径和是多少。

我们做算法题的时候，一定要尽量举一反三。我感觉今天的问题和最小路径和有关吧？

最小化骑士的初始生命值是否意味着最大化骑士路径上的血瓶数量？是不是相当于求“最大路径和”？计算“最小路径和”的思想可以直接套用吗？

但想了想，我发现这个推论并不成立。吃最多的血瓶并不一定会导致初始健康值最小。

例如，在下面的情况下，如果你想吃掉最多的血瓶以获得“最大路径总和”，那么你应该沿着下图箭头所示的路径走，并且初始生命值需要为11：

但也容易看出，正确答案应该是下图箭头所示的路径，并且初始健康值只需要1：

所以，关键不是吃掉最多的血瓶，而是损失最少的生命值。

对于这种最优值问题，必须采用动态规划技术，合理设计dp数组/函数的定义。与之前的最小路径和问题类比，dp 函数签名必须如下所示：

intdp(int[][]grid,inti,intj);不过这题中dp函数的定义比较有趣。按照常理，这个dp函数的定义应该是：

从左上角（grid[0][0]）走到grid[i][j]至少需要dp(grid, i, j)个生命值。

如果这样定义，基本情况是当i 和j 等于0 时，我们可以编写这样的代码：

intcalculateMinimumHP(int[][]grid){intm=grid.length;intn=grid[0].length;//我们要计算从左上角到右下角所需的最小生命值returndp(grid, m-1,n -1);}intdp(int[][]grid,inti,intj){//basecaseif(i==0j==0){//只要保证骑士在他的时候不死即可落地returngird[i][j]0?1: -grid[i][j]+1;}.}PS: 为了简单起见，dp(grid, i, j) 将简写为dp(i ，j) 从现在开始，让大家都能明白。

接下来我们需要找到状态转换。你还记得如何求状态转移方程吗？我们这样定义dp函数是否可以正确地进行状态转移呢？

我们希望能够通过dp(i-1,j)和dp(i,j-1)导出dp(i,j)，这样我们就可以继续逼近base case，并且可以正确地进行状态转换。

具体来说，“最低达到A的生命值”应该由“最低达到B的生命值”和“最低达到C的生命值”推算出来：

但问题是，能推出去吗？事实上这是不可能的。

因为根据dp函数的定义，你只知道“从左上角可以到达B的最小生命值”，但不知道“到达B时的生命值”。

“到达B时的健康值”是状态转移的必要参考。我给你举个例子你就会明白。假设以下情况：

您认为在这种情况下骑士拯救公主的最佳方法是什么？

显然顺着图中的蓝线去B，最后去A吧？这样初始血量只需要1；如果走黄色箭头路径，先去C，再去A，初始血量将至少需要6。

为什么会发生这种情况？骑士走到B和C的最低初始血量都是1。为什么他最终从B走到A而不是从C走到A？

因为骑士到达B时生命值是11，到达C时生命值依然是1。

如果骑士坚持从C走到A，那么初始血量必须增加到6点；如果他从B走到A，初始血量是1，这已经足够了，因为他在途中吃了血瓶。抵抗A以上怪物的伤害。

现在这一点应该很清楚了。让我们回顾一下dp 函数的定义。上图中，算法只知道dp(1, 2)=dp(2, 1)=1。它们都是一样的。如何做出正确的决定是计算dp(2, 2)？

因此，我们之前对dp数组的定义是错误的，信息量不足，算法无法做出正确的状态转换。

正确的做法需要逆向思维，依然是下面的dp函数：

intdp(int[][]grid,inti,intj);但我们需要修改dp函数的定义：

从grid[i][j]到达终点（右下角）所需的最少生命数为dp(grid, i, j)。

然后你可以这样写代码：

intcalculateMinimumHP(int[][]grid){//我们要计算从左上角到右下角所需的最小生命值returndp(grid,0,0);}intdp(int[][]grid, inti,intj){ intm=grid.length;intn=grid[0].length;//basecaseif(i==m-1j==n-1){returngrid[i][j]=0?1:-grid [i][j ]+1;}.} 根据新的dp 函数定义和基本情况，如果我们想找到dp(0, 0)，我们应该尝试使用dp(i, j+1)和dp(i+1, j ) 推导dp(i, j)，这样我们就可以不断逼近基本情况并正确执行状态转换。

具体来说，“A到右下角的最小生命值”应该由“B到右下角的最小生命值”和“C到右下角的最小生命值”推导出来：

可以推论吗？这次有可能了。假设dp(0, 1)=5，dp(1, 0)=4，那么你肯定可以从A 到C，因为4 小于5。

那么如何推导出dp(0, 0) 是什么？

假设A的值为1。由于我们知道下一步是去C，而dp(1, 0)=4意味着当我们到达grid[1][0时，我们必须至少有4个健康点]，那么我们可以确定骑士需要4 - 1=3点初始生命值才能出现在A点，对吧。

那么如果A的值为10的话，落地的时候就可以捡到一个大血瓶，这就超出了后续的需要。 4 - 10=-6 表示骑士的初始生命值为负数。这显然是不允许的。骑士的生命值小于1就死了，所以在这种情况下骑士的初始生命值应该是1。

综上，导出了状态转移方程：

intres=min(dp(i+1,j),dp(i,j+1))-grid[i][j];dp(i,j)=res=0?1:res;根据这个核心逻辑，添加一个备忘录消除了重叠的子问题，最终的代码可以直接编写：