C/C++ 动态规划入门：二维路径问题实战解析

2. 不同路径 II（带障碍）

题目描述

在上题基础上，网格中增加了障碍物。机器人不能经过障碍物，求路径数。

思路分析

核心逻辑不变，只需增加对障碍物的判断。如果当前位置是障碍物，则 dp[i][j] = 0，相当于切断了路径。

注意：遇到障碍物时跳过计算，保持该位置为初始值 0 即可。

代码实现

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        // 使用 dp 表存储路径数，默认初始化为 0
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        // 同样利用 dp[0][1]=1 来初始化第一行
        dp[0][1] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果当前格子是障碍物，路径数为 0，直接 continue
                if (obstacleGrid[i - 1][j - 1] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n][m];
    }
};

3. 珠宝的最高价值

题目描述

从左上角走到右下角，每个格子有对应的珠宝价值，求能拿到的最大总价值。

思路分析

这是求最大值的问题，状态转移方程需要取 max。

1. 状态定义：dp[i][j] 表示到达 (i, j) 时能获得的最大价值。
2. 转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1]。
3. 初始化：由于是求最大值且边缘可以从上或左过来，DP 表初始化为 0 即可，无需特殊填充。

代码实现

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n = frame.size(), m = frame[0].size();
        // 多开一行一列，默认值为 0
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 取上方和左方的最大值，加上当前格子的价值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
};

4. 下降路径最小和

题目描述

从第一行任意元素出发，每次可以移动到下一行的相邻元素（左下、正下、右下），求到达最后一行的最小路径和。

思路分析

这道题稍微复杂一点，因为每个点有三个来源方向，且要求最小值。

1. 状态定义：dp[i][j] 表示到达 (i, j) 的最小下降路径和。
2. 转移方程：dp[i][j] = min(三个方向的上层值) + matrix[i-1][j-1]。
3. 初始化难点：因为是求最小值，不能简单初始化为 0，否则会被误判为最优解。通常初始化为无穷大，然后单独处理第一行。
4. 边界处理：为了防止访问越界，DP 表可以多开两列，或者在代码中做边界判断。

代码实现

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 多开一行两列，全部初始化为 INT_MAX，防止越界干扰最小值计算
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        
        // 初始化第一行为 0，作为起始点
        for (int i = 0; i < n + 2; i++) dp[0][i] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 取左下、正下、右下三个方向的最小值
                int m = min(dp[i - 1][j - 1], dp[i - 1][j]);
                dp[i][j] = min(m, dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        
        // 返回最后一行的最小值
        int retmin = INT_MAX;
        for (int i = 1; i <= n; i++) {
            retmin = min(retmin, dp[n][i]);
        }
        return retmin;
    }
};

5. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格，找出一条从左上到右下的路径，使得路径上的数字总和最小。

思路分析

与'不同路径'类似，但这里是求和最小值。初始化策略很关键。

1. 状态定义：dp[i][j] 表示以 (i, j) 结尾的最小路径和。
2. 转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]。
3. 初始化技巧：为了避免单独处理第一行和第一列，可以将 DP 表多开一行一列，并初始化为 INT_MAX，然后将 dp[0][1] 和 dp[1][0] 设为 0。这样在循环中，第一行和第一列的值会自然由 0 累加而来。

代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // 多创建一行一列，初始化为 INT_MAX
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        
        // 设置虚拟起点，让第一行和第一列能正常累加
        dp[0][1] = dp[1][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
};

6. 地下城游戏

题目描述

骑士需要从左上角出发到达右下角拯救公主。每个房间可能有伤害或增益。骑士的健康点数不能降到 0 或以下。求骑士出发时的最低初始健康点数。

思路分析

这道题比较特殊，正向推导（从起点到终点）很难确定初始血量，因为后续的伤害未知。逆向思维是关键：从终点倒推回起点。

1. 状态定义：dp[i][j] 表示从 (i, j) 出发到达终点所需的最低初始健康点数。
2. 转移方程：dp[i][j] = min(右边所需，下边所需) - dungeon[i][j]。
   • 如果减完结果是负数，说明当前房间给的增益足够抵消后续需求，此时只需要 1 点血即可（最低生命值为 1）。
   • 所以公式修正为：max(min(...), 1)。
3. 初始化：终点处，如果 dungeon 是负数（伤害），则需要额外血量；如果是正数（增益），则至少需要 1 点。为了方便，我们在 DP 表外圈设 dp[n][m-1]=1, dp[n-1][m]=1 作为边界条件。
4. 遍历顺序：从下往上，从右往左。

代码实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        // 多开一圈，初始化为 INT_MAX
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        
        // 边界初始化，保证终点计算正确
        dp[n - 1][m] = 1;
        dp[n][m - 1] = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                // 取右边和下边的最小需求
                int minNeed = min(dp[i + 1][j], dp[i][j + 1]);
                // 减去当前房间的值
                dp[i][j] = minNeed - dungeon[i][j];
                // 保证健康值至少为 1
                dp[i][j] = max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

总结

通过以上六个案例，我们可以总结出二维路径类 DP 的几个关键点：

1. 状态定义决定方向：正向还是逆向？是从起点开始还是向终点结束？这取决于题目是否具备'无后效性'。像地下城游戏这种受未来影响大的，必须逆向。
2. 初始化要谨慎：求最大值通常初始化为 0，求最小值要注意不要初始化为 0（除非有特定逻辑），可能需要用 INT_MAX 配合边界填充技巧。
3. 边界处理：多开一行一列往往能省去大量的 if 判断，让代码更简洁。
4. 空间优化：虽然本文主要展示二维 DP 表，但在实际工程中，很多路径问题可以通过滚动数组将空间复杂度降为一维。

掌握这些模式，面对类似的网格 DP 问题时就能游刃有余了。