动态规划_路径问题（典型算法思想）—— 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)，初始化为 0vector<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) 的唯一路径数。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

2. 动态规划定义：

   • 定义 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)。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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];}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

   • 当 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)，初始化为 0vector<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) 的唯一路径数。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

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

2. 动态规划定义：

   • 定义 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。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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];}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

   • 当 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)，初始化为 0vector<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) 能够收集到的珠宝的最大价值。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

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

2. 动态规划定义：

   • 定义 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)，所以取上方和左方的最大值，并加上当前格子的价值。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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];}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

   • 当 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_MAXvector<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 的矩阵，从第一行的任意位置出发，每次可以向下、向左下或向右下移动，求到达最后一行的最小路径和。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

2. 动态规划定义：

   • 定义 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)。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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;}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

   • 当 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_MAXvector<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) 的最小路径和。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

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

2. 动态规划定义：

   • 定义 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)，所以取上方和左方的最小值，并加上当前格子的值。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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];}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

   • 当 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_MAXvector<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 的地下城网格，每个格子中有一个整数（正数表示增加健康值，负数表示减少健康值），骑士从左上角出发，每次只能向右或向下移动，求骑士需要的最小初始健康值，以确保能够到达右下角的公主位置。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

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

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

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

2. 动态规划定义：

   • 定义 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。

3. 边界条件：

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

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

4. 填表过程：

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

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

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

5. 返回结果：

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

---

代码优化思路

1. 空间优化：

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

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

2. 滚动数组优化：

   • 使用两个一维数组 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];}
};

---

优化后的代码分析

1. 空间复杂度：

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

2. 时间复杂度：

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

3. 边界条件处理：

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

---

总结

• 原始代码：

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

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

• 优化后的代码：

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

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