「魔塔」这是一款经典的地牢游戏，碰怪物要掉血，吃血瓶可以加血，你要收钥匙，一层一层上楼，最后救出美丽的公主。

手机上还能玩这个游戏：

嗯，我相信这个游戏承包了很多人的童年记忆。我记得当我还是个孩子的时候，一个人用游戏机玩，两三个人围着左右手指画脚，这导致玩游戏的人体验很差，左右人都很开心

力扣第 174 题是一道类似的题目，我简单描述一下：

输入存储整数的二维数组grid，如果grid[i][j] > 0.说明这个格子里装着血瓶，通过它可以增加相应的生命值；如果grid[i][j] == 0.这是一个空格子，不会发生在它之后；如果grid[i][j] < 0.说明这个格子里有怪物，通过它会失去相应的生命值。

现在你是骑士，会出现在最上角，公主被困在最右下角，你只能向右和向下移动，骑士最初的生命值至少是多少，为了成功拯救公主？

换句话说，问你至少需要多少初始生命值，可以让骑士从最左上角移动到最右下角，任何时候生命值都大于 0。

函数签名如下：

intcalculateMinimumHP(int[][]grid);

例如，给我们一个主题的例子，输入以下二维数组grid，用K表示骑士，用P表示公主:

算法应返回 也就是说，骑士的初始生命值至少是 7 成功救出公主，行进路线如图中箭头所示。

上篇文章 最小路径和 写过类似的问题，问你从左上角到右下角的最小路径和是多少。

我们必须算法题时，我们必须试着从一个例子中得出推论最小的路径有关，对吧？

最小化骑士的初始生命值是否意味着最大化骑士路线上的血瓶？这相当于寻求吗？「最大路径和」？计算是否可以直接应用「最小路径和」的思路？

但经过一点思考，我发现这个推论是站不住脚的。吃最多的血瓶可能无法获得最小的初始生命值。

例如，在以下情况下，如果你想吃最多的血瓶「最大路径和」，根据下图箭头所示的路径，需要初始生命值 11：

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

因此，关键不在于吃最多的血瓶，而在于如何失去最少的生命值。

这动态规划技巧的帮助下，必须合理设计这类问题。dp数组/函数的定义。类比前面 最小路径和问题，dp函数签名必须长这样：

intdp(int[][]grid,inti,intj);

但这个问题是对的dp根据常识，函数的定义更有趣dp函数的定义应为：

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

这样定义，base case 就是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==0&&j==0){///确保骑士不会死。returngird[i][j]>0?1:-grid[i][j] 1;}...}

PS：为了简洁，之后dp(grid, i, j)就简写为dp(i, j)，大家理解就好。

接下来，我们需要找到状态转移。还记得如何找到状态转移方程吗？我们这样定义dp函数能否正确转移状态？

我们希望dp(i, j)能够通过dp(i-1, j)和dp(i, j-1)推导出来，这样才能不断逼近 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-1&&j==n-1){returngrid[i][j]>=0?1:-grid[i][j] 1;}...}

根据新的dp函数定义和 base case，我们想求dp(0, 0)应该试着通过dp(i, j 1)和dp(i 1, j)推导出dp(i, j)，这样才能不断逼近 base case，正确的状态转移。

具体来说，「从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 如果你点击生命值，你可以确定骑士需要出现在A点 4 - 1 = 3 点击初始生命值，对吧？

假如A的值是 10.着陆后可以找到一个超出后续需求的大血瓶。 - 10 = -6 这意味着骑士的初始生命值为负，这显然是不可能的。骑士的生命值小于 1 所以在这种情况下，骑士的初始生命值应该是 1。

综上所述，已经推出了状态转移方程:

intres=min(dp(i 1,j),dp(i,j 1))-grid[i][j];dp(i,j)=res<=0?1:res;

根据这加备忘录来消除重叠子问题，可以直接编写最终代码：

/*主函数*/intcalculateMinimumHP(int[][]grid){intm=grid.length;intn=grid[0].length;//备忘录初始化为-1memo=newint[m][n];for(int[]row:memo){Arrays.fill(row,-1);}returndp(grid,0,0);}//备忘录，消除重叠子问题int[][]memo;/*定义：从(i, j)到达右下角至少需要初始血量*/intdp(int[][]grid,inti,intj){intm=grid.length;intn=grid[0].length;//basecaseif(i==m-1&&j==n-1){returngrid[i][j]>=0?1:-grid[i][j] 1;}if(i==m||j==n){returnInteger.MAX_VALUE;}//避免重复计算if(memo[i][j]!=-1){returnmemo[i][j];}//状态转移逻辑intres=Math.min(dp(grid,i,j 1),dp(grid,i 1,j))-grid[i][j];///骑士的生命值至少为1memo[i][j]=res<=0?=-1){returnmemo[i][j];}//状态转移逻辑intres=Math.min(dp(grid,i,j 1),dp(grid,i 1,j))-grid[i][j];///骑士的生命值至少为1memo[i][j]=res<=0?1:res;returnmemo[i][j];}

这是自上而下带备忘录的动态规划解决方案，参考上述内容 详细说明动态规划套路 很容易改写成dp这里不写数组的迭代解法，读者可以试着自己写。

这个问题的核心是定义dp函数，找到正确的状态转移方程，从而计算正确的答案。

来源：https://mp.weixin.qq.com/s/KD5sS_wbwiWH0rObuya7aA