动态规划_路径问题（典型算法思想）——OJ例题算法解析思路

目录

一、62. 不同路径 - 力扣（LeetCode）

算法代码： 

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

二、 63. 不同路径 II - 力扣（LeetCode）

算法代码： 

代码思路分析​编辑

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

三、 LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

算法代码： 

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

四、 931. 下降路径最小和 - 力扣（LeetCode）

算法代码： 

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

五、64. 最小路径和 - 力扣（LeetCode）

算法代码：

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

六、 174. 地下城游戏 - 力扣（LeetCode）

算法代码：

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

---

一、62. 不同路径 - 力扣（LeetCode）

算法代码：  class Solution { public: int uniquePaths(int m, int n) { // 创建 dp 表，大小为 (m+1) x (n+1)，初始化为 0 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化 dp[0][1] = 1; // 虚拟初始化，保证 dp[1][1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // 返回结果 return dp[m][n]; } };

         这段代码解决的问题是：机器人从网格的左上角到右下角的唯一路径数。给定一个 m x n 的网格，机器人每次只能向右或向下移动，求从起点 (0, 0) 到终点 (m-1, n-1) 的唯一路径数。以下是代码的思路分析：

---

代码思路分析

问题定义：

机器人从网格的左上角 (0, 0) 出发，每次只能向右或向下移动。

网格的大小为 m x n，求从起点到终点的唯一路径数。

动态规划定义：

定义 dp[i][j] 表示从起点 (0, 0) 到位置 (i-1, j-1) 的唯一路径数。

状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

因为机器人只能从上方 (i-1, j) 或左方 (i, j-1) 移动到当前位置 (i, j)。

边界条件：

dp[0][1] = 1：这是一个虚拟的初始化值，用于保证 dp[1][1] 的正确计算。

实际网格的起点是 (1, 1)，对应 dp[1][1]。

填表过程：

从 i = 1 到 m，从上往下逐行填表。

从 j = 1 到 n，从左往右逐列填表。

每次计算 dp[i][j] 时，累加上方和左方的路径数。

返回结果：

最终返回 dp[m][n]，即从起点 (0, 0) 到终点 (m-1, n-1) 的唯一路径数。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (m+1) x (n+1) 的二维数组 dp，空间复杂度为 O(m x n)。

由于每次计算 dp[i][j] 只需要上一行和当前行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 prev 和 curr，分别表示上一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 prev，继续计算下一行。

---

优化后的代码 class Solution { public: int uniquePaths(int m, int n) { // 使用滚动数组优化 vector<int> prev(n + 1, 0); // 上一行 vector<int> curr(n + 1, 0); // 当前行 // 初始化 prev[1] = 1; // 虚拟初始化，保证 curr[1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 curr[j] = prev[j] + curr[j - 1]; } prev = curr; // 更新上一行 } // 返回结果 return curr[n]; } };

---

优化后的代码分析 空间复杂度：

从 O(m x n) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(m x n)，因为需要遍历整个网格。

边界条件处理：

当 m = 1 或 n = 1 时，直接返回 1，因为只有一条路径。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(m x n)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。

二、 63. 不同路径 II - 力扣（LeetCode）

算法代码：  class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& ob) { int m = ob.size(), n = ob[0].size(); // 创建 dp 表，大小为 (m+1) x (n+1)，初始化为 0 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化 dp[1][0] = 1; // 虚拟初始化，保证 dp[1][1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 if (ob[i - 1][j - 1] == 0) { // 如果当前位置没有障碍物 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } // 返回结果 return dp[m][n]; } };

         这段代码解决的问题是：带障碍物的网格中，机器人从左上角到右下角的唯一路径数。给定一个 m x n 的网格，其中某些格子有障碍物（用 1 表示），机器人每次只能向右或向下移动，求从起点 (0, 0) 到终点 (m-1, n-1) 的唯一路径数。以下是代码的思路分析：

---

代码思路分析 问题定义：

机器人从网格的左上角 (0, 0) 出发，每次只能向右或向下移动。

网格中有障碍物（1 表示障碍物，0 表示可通行）。

求从起点到终点的唯一路径数。

动态规划定义：

定义 dp[i][j] 表示从起点 (0, 0) 到位置 (i-1, j-1) 的唯一路径数。

状态转移方程：

如果 ob[i-1][j-1] = 0（即当前位置没有障碍物），则 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

如果 ob[i-1][j-1] = 1（即当前位置有障碍物），则 dp[i][j] = 0。

边界条件：

dp[1][0] = 1：这是一个虚拟的初始化值，用于保证 dp[1][1] 的正确计算。

实际网格的起点是 (1, 1)，对应 dp[1][1]。

填表过程：

从 i = 1 到 m，从上往下逐行填表。

从 j = 1 到 n，从左往右逐列填表。

每次计算 dp[i][j] 时，检查当前位置是否有障碍物：

如果没有障碍物，则累加上方和左方的路径数。

如果有障碍物，则 dp[i][j] = 0。

返回结果：

最终返回 dp[m][n]，即从起点 (0, 0) 到终点 (m-1, n-1) 的唯一路径数。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (m+1) x (n+1) 的二维数组 dp，空间复杂度为 O(m x n)。

由于每次计算 dp[i][j] 只需要上一行和当前行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 prev 和 curr，分别表示上一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 prev，继续计算下一行。

---

优化后的代码 class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& ob) { int m = ob.size(), n = ob[0].size(); // 使用滚动数组优化 vector<int> prev(n + 1, 0); // 上一行 vector<int> curr(n + 1, 0); // 当前行 // 初始化 prev[1] = 1; // 虚拟初始化，保证 curr[1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 if (ob[i - 1][j - 1] == 0) { // 如果当前位置没有障碍物 curr[j] = prev[j] + curr[j - 1]; } else { curr[j] = 0; // 如果当前位置有障碍物，路径数为 0 } } prev = curr; // 更新上一行 } // 返回结果 return curr[n]; } };

---

优化后的代码分析 空间复杂度：

从 O(m x n) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(m x n)，因为需要遍历整个网格。

边界条件处理：

当 m = 1 或 n = 1 时，直接返回 1，因为只有一条路径（如果没有障碍物）。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(m x n)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。

三、 LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

算法代码：  class Solution { public: int jewelleryValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // 创建 dp 表，大小为 (m+1) x (n+1)，初始化为 0 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; } } // 返回结果 return dp[m][n]; } };

        这段代码解决的问题是：在网格中从左上角到右下角收集珠宝的最大价值。给定一个 m x n 的网格，每个格子中有一个珠宝的价值，机器人每次只能向右或向下移动，求从起点 (0, 0) 到终点 (m-1, n-1) 能够收集到的珠宝的最大价值。以下是代码的思路分析：

---

代码思路分析

问题定义：

机器人从网格的左上角 (0, 0) 出发，每次只能向右或向下移动。

每个格子 (i, j) 中有一个珠宝的价值 grid[i][j]。

求从起点到终点能够收集到的珠宝的最大价值。

动态规划定义：

定义 dp[i][j] 表示从起点 (0, 0) 到位置 (i-1, j-1) 能够收集到的珠宝的最大价值。

状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

因为机器人只能从上方 (i-1, j) 或左方 (i, j-1) 移动到当前位置 (i, j)，所以取上方和左方的最大值，并加上当前格子的价值。

边界条件：

dp[0][j] 和 dp[i][0] 都初始化为 0，因为从起点外的地方无法到达起点。

实际网格的起点是 (1, 1)，对应 dp[1][1]。

填表过程：

从 i = 1 到 m，从上往下逐行填表。

从 j = 1 到 n，从左往右逐列填表。

每次计算 dp[i][j] 时，取上方和左方的最大值，并加上当前格子的价值。

返回结果：

最终返回 dp[m][n]，即从起点 (0, 0) 到终点 (m-1, n-1) 能够收集到的珠宝的最大价值。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (m+1) x (n+1) 的二维数组 dp，空间复杂度为 O(m x n)。

由于每次计算 dp[i][j] 只需要上一行和当前行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 prev 和 curr，分别表示上一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 prev，继续计算下一行。

---

优化后的代码 class Solution { public: int jewelleryValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // 使用滚动数组优化 vector<int> prev(n + 1, 0); // 上一行 vector<int> curr(n + 1, 0); // 当前行 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 curr[j] = max(prev[j], curr[j - 1]) + grid[i - 1][j - 1]; } prev = curr; // 更新上一行 } // 返回结果 return curr[n]; } };

---

优化后的代码分析 空间复杂度：

从 O(m x n) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(m x n)，因为需要遍历整个网格。

边界条件处理：

当 m = 1 或 n = 1 时，直接累加路径上的珠宝价值即可。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(m x n)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。

四、 931. 下降路径最小和 - 力扣（LeetCode）

算法代码：  class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int n = matrix.size(); // 创建 dp 表，大小为 (n+1) x (n+2)，初始化为 INT_MAX vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX)); // 初始化第 0 行 for (int j = 0; j < n + 2; j++) dp[0][j] = 0; // 填表 for (int i = 1; i <= n; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1]; } } // 返回结果 int ret = INT_MAX; for (int j = 1; j <= n; j++) ret = min(ret, dp[n][j]); return ret; } };

        这段代码解决的问题是：在矩阵中找到下降路径的最小和。给定一个 n x n 的矩阵，从第一行的任意位置出发，每次可以向下、向左下或向右下移动，求到达最后一行的最小路径和。以下是代码的思路分析：

---

代码思路分析

问题定义：

从矩阵的第一行的任意位置出发，每次可以向下、向左下或向右下移动。

求到达最后一行的最小路径和。

动态规划定义：

定义 dp[i][j] 表示从第一行到位置 (i-1, j-1) 的最小路径和。

状态转移方程：

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1]

因为可以从左上方 (i-1, j-1)、正上方 (i-1, j) 或右上方 (i-1, j+1) 移动到当前位置 (i, j)。

边界条件：

dp[0][j] = 0：表示从虚拟的第 0 行出发的路径和为 0。

dp[i][0] 和 dp[i][n+1] 初始化为 INT_MAX，表示这些位置不可达。

填表过程：

从 i = 1 到 n，从上往下逐行填表。

从 j = 1 到 n，从左往右逐列填表。

每次计算 dp[i][j] 时，取左上方、正上方和右上方的最小值，并加上当前格子的值。

返回结果：

最终返回 dp[n][j] 的最小值，即从第一行到最后一行的最小路径和。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (n+1) x (n+2) 的二维数组 dp，空间复杂度为 O(n^2)。

由于每次计算 dp[i][j] 只需要上一行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 prev 和 curr，分别表示上一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 prev，继续计算下一行。

---

优化后的代码 class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int n = matrix.size(); // 使用滚动数组优化 vector<int> prev(n + 2, 0); // 上一行 vector<int> curr(n + 2, 0); // 当前行 // 填表 for (int i = 1; i <= n; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 curr[j] = min(prev[j - 1], min(prev[j], prev[j + 1])) + matrix[i - 1][j - 1]; } prev = curr; // 更新上一行 } // 返回结果 int ret = INT_MAX; for (int j = 1; j <= n; j++) ret = min(ret, curr[j]); return ret; } };

---

优化后的代码分析 空间复杂度：

从 O(n^2) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(n^2)，因为需要遍历整个矩阵。

边界条件处理：

当 n = 1 时，直接返回矩阵中的唯一值。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(n^2)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。

 

五、64. 最小路径和 - 力扣（LeetCode）

算法代码： class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // 创建 dp 表，大小为 (m+1) x (n+1)，初始化为 INT_MAX vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 初始化 dp[0][1] = 0; // 虚拟初始化，保证 dp[1][1] 的正确计算 dp[1][0] = 0; // 虚拟初始化，保证 dp[1][1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; } } // 返回结果 return dp[m][n]; } };

        这段代码解决的问题是：在网格中找到从左上角到右下角的最小路径和。给定一个 m x n 的网格，每个格子中有一个非负整数，机器人每次只能向右或向下移动，求从起点 (0, 0) 到终点 (m-1, n-1) 的最小路径和。以下是代码的思路分析：

---

代码思路分析

问题定义：

机器人从网格的左上角 (0, 0) 出发，每次只能向右或向下移动。

每个格子 (i, j) 中有一个非负整数 grid[i][j]，表示通过该格子的成本。

求从起点到终点的最小路径和。

动态规划定义：

定义 dp[i][j] 表示从起点 (0, 0) 到位置 (i-1, j-1) 的最小路径和。

状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

因为机器人只能从上方 (i-1, j) 或左方 (i, j-1) 移动到当前位置 (i, j)，所以取上方和左方的最小值，并加上当前格子的值。

边界条件：

dp[0][1] = 0 和 dp[1][0] = 0：这是虚拟的初始化值，用于保证 dp[1][1] 的正确计算。

实际网格的起点是 (1, 1)，对应 dp[1][1]。

填表过程：

从 i = 1 到 m，从上往下逐行填表。

从 j = 1 到 n，从左往右逐列填表。

每次计算 dp[i][j] 时，取上方和左方的最小值，并加上当前格子的值。

返回结果：

最终返回 dp[m][n]，即从起点 (0, 0) 到终点 (m-1, n-1) 的最小路径和。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (m+1) x (n+1) 的二维数组 dp，空间复杂度为 O(m x n)。

由于每次计算 dp[i][j] 只需要上一行和当前行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 prev 和 curr，分别表示上一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 prev，继续计算下一行。

---

优化后的代码 class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // 使用滚动数组优化 vector<int> prev(n + 1, INT_MAX); // 上一行 vector<int> curr(n + 1, INT_MAX); // 当前行 // 初始化 prev[1] = 0; // 虚拟初始化，保证 curr[1] 的正确计算 // 填表 for (int i = 1; i <= m; i++) { // 从上往下 for (int j = 1; j <= n; j++) { // 从左往右 curr[j] = min(prev[j], curr[j - 1]) + grid[i - 1][j - 1]; } prev = curr; // 更新上一行 } // 返回结果 return curr[n]; } };

---

优化后的代码分析 空间复杂度：

从 O(m x n) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(m x n)，因为需要遍历整个网格。

边界条件处理：

当 m = 1 或 n = 1 时，直接累加路径上的值即可。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(m x n)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。

六、 174. 地下城游戏 - 力扣（LeetCode）

算法代码： class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(), n = dungeon[0].size(); // 创建 dp 表，大小为 (m+1) x (n+1)，初始化为 INT_MAX vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 初始化 dp[m][n - 1] = 1; // 虚拟初始化，保证 dp[m-1][n-1] 的正确计算 dp[m - 1][n] = 1; // 虚拟初始化，保证 dp[m-1][n-1] 的正确计算 // 填表 for (int i = m - 1; i >= 0; i--) { // 从下往上 for (int j = n - 1; j >= 0; j--) { // 从右往左 dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]; dp[i][j] = max(1, dp[i][j]); // 确保健康值不小于 1 } } // 返回结果 return dp[0][0]; } };

        这段代码解决的问题是：地下城游戏中的最小初始健康值。给定一个 m x n 的地下城网格，每个格子中有一个整数（正数表示增加健康值，负数表示减少健康值），骑士从左上角出发，每次只能向右或向下移动，求骑士需要的最小初始健康值，以确保能够到达右下角的公主位置。以下是代码的思路分析：

---

代码思路分析

问题定义：

骑士从网格的左上角 (0, 0) 出发，每次只能向右或向下移动。

每个格子 (i, j) 中有一个整数 dungeon[i][j]，表示骑士的健康值变化（正数增加，负数减少）。

求骑士需要的最小初始健康值，以确保在移动过程中健康值始终大于 0，并能够到达右下角的公主位置。

动态规划定义：

定义 dp[i][j] 表示从位置 (i, j) 到终点 (m-1, n-1) 所需的最小初始健康值。

状态转移方程：

dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]

因为骑士只能从下方 (i+1, j) 或右方 (i, j+1) 移动到当前位置 (i, j)，所以取下方和右方的最小值，并减去当前格子的值。

如果 dp[i][j] 小于 1，则将其设置为 1，因为骑士的健康值必须始终大于 0。

边界条件：

dp[m][n-1] = 1 和 dp[m-1][n] = 1：这是虚拟的初始化值，用于保证 dp[m-1][n-1] 的正确计算。

实际网格的终点是 (m-1, n-1)，对应 dp[m-1][n-1]。

填表过程：

从 i = m-1 到 0，从下往上逐行填表。

从 j = n-1 到 0，从右往左逐列填表。

每次计算 dp[i][j] 时，取下方和右方的最小值，并减去当前格子的值，然后确保 dp[i][j] 不小于 1。

返回结果：

最终返回 dp[0][0]，即从起点 (0, 0) 到终点 (m-1, n-1) 所需的最小初始健康值。

---

代码优化思路 空间优化：

当前代码使用了一个大小为 (m+1) x (n+1) 的二维数组 dp，空间复杂度为 O(m x n)。

由于每次计算 dp[i][j] 只需要下一行和当前行的值，可以用滚动数组优化，将空间复杂度降低到 O(n)。

滚动数组优化：

使用两个一维数组 next 和 curr，分别表示下一行和当前行的值。

每次计算完当前行后，将 curr 赋值给 next，继续计算上一行。

---

优化后的代码 class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(), n = dungeon[0].size(); // 使用滚动数组优化 vector<int> next(n + 1, INT_MAX); // 下一行 vector<int> curr(n + 1, INT_MAX); // 当前行 // 初始化 next[n - 1] = 1; // 虚拟初始化，保证 curr[n-1] 的正确计算 // 填表 for (int i = m - 1; i >= 0; i--) { // 从下往上 for (int j = n - 1; j >= 0; j--) { // 从右往左 curr[j] = min(next[j], curr[j + 1]) - dungeon[i][j]; curr[j] = max(1, curr[j]); // 确保健康值不小于 1 } next = curr; // 更新下一行 } // 返回结果 return curr[0]; } };

---

优化后的代码分析 空间复杂度：

从 O(m x n) 降低到 O(n)，只使用了两个一维数组。

时间复杂度：

仍然是 O(m x n)，因为需要遍历整个网格。

边界条件处理：

当 m = 1 或 n = 1 时，直接累加路径上的值即可。

---

总结 原始代码：

使用二维动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

空间复杂度为 O(m x n)。

优化后的代码：

使用滚动数组优化，空间复杂度降低到 O(n)。

适合对空间复杂度有要求的场景。