Leetcode第174题地牢游戏代码测试通过但提交失败求助

• 类静态变量min_hp状态污染
  你定义的min_hp是类级别的静态变量，LeetCode运行所有测试用例时不会主动重置类静态变量，跑完第一个测试用例后min_hp会保留上一个用例的运行结果，后续测试用例运行时，init_hp > Solution.min_hp and Solution.min_hp != 0的判断逻辑会直接错误返回，结果完全不符合预期。这也是你单测能过、提交批量测试过不了的最直接原因。

• 暴力递归时间复杂度过高
  你采用的暴力回溯方案时间复杂度为O(2^(m+n))，m和n为网格的长宽，只要测试用例的网格尺寸超过10x10，代码就会触发超时限制，根本跑不完所有测试用例。

• 坐标判断逻辑错误
  代码里判断到达右下角终点的条件写反了：

elif pos_x + 1 == len(dungeon) and pos_y + 1 == len(dungeon[0]):

其中len(dungeon)是网格的行数（对应y轴的最大值），len(dungeon[0])是网格的列数（对应x轴的最大值），正确的终点判断应该是pos_x + 1 == len(dungeon[0]) and pos_y + 1 == len(dungeon)，错误的判断会导致部分路径无法正确识别终点，返回错误结果。

• 正序搜索逻辑存在天生缺陷
  地牢游戏的核心特点是后续路径的大额扣血会直接决定初始血量的最小值，你采用从左上角到右下角的正序搜索，无法预判后续路径的扣血情况，很容易得到非最优的初始血量结果，复杂场景下必然逻辑出错。

• 血量补全逻辑效率极低
  当init_hp + damage <= 0时你每次只给init_hp加1然后递归重跑当前格子，如果当前格子扣血量很高，这个逻辑会产生大量无效递归，进一步加剧超时问题。

直接改用这道题的标准倒序动态规划解法即可，核心思路是定义dp[i][j]为从坐标(i,j)走到终点需要的最小初始血量，从右下角开始往左上角递推，状态转移方程为：
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
时间复杂度可以降到O(mn)，空间复杂度还能优化到O(min(m,n))，完全满足LeetCode的提交要求。

内容的提问来源于stack exchange，提问作者bmorozov