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

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

题目描述： 网格中某些格子包含障碍物。机器人不能经过障碍物。求路径数。

思路分析： 逻辑与上一题基本一致，区别在于遇到障碍物时的处理。

1. 状态定义：同上。
2. 转移方程：如果当前格子是障碍物，则无法到达该点，路径数为 0。否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 初始化：同样使用虚拟行列技巧。注意如果起点或终点本身有障碍物，直接返回 0。
4. 细节：在循环中遇到障碍物时，跳过当前格子的计算（保持默认值 0），后续格子自然无法从该点转移。

代码实现：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        // 如果起点或终点有障碍，直接无路可走
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][1] = 1; // 虚拟起点

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 对应原网格的坐标是 i-1, j-1
                if (obstacleGrid[i - 1][j - 1] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

3. 珠宝的最高价值

题目描述： 在一个 m x n 的棋盘中，每个格子放有一定价值的珠宝。从左上角走到右下角，求能拿到的最大价值总和。

思路分析： 这是典型的'最大值'类 DP 问题。

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. 初始化：由于要求最大值且边缘格子没有前驱，使用虚拟行列并将默认值设为 0 即可满足逻辑。
4. 注意：本题不需要像路径计数那样特殊初始化 dp[0][1]=1，因为价值累加是从 0 开始的。

代码实现：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        
        // 多开一行一列，默认值为 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]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

4. 下降路径最小和

题目描述： 给定一个方阵，从第一行任意元素出发，每次移动到下一行的相邻元素（正下方、左下、右下），求路径和的最小值。

思路分析： 这道题增加了移动方向的限制（三个方向），且需要处理边界越界问题。

1. 状态定义：dp[i][j] 表示到达 (i, j) 位置的最小下降路径和。
2. 转移方程：dp[i][j] = min(上左，上，上右) + matrix[i-1][j-1]。
3. 初始化难点：因为是求最小值，不能简单地将边界初始化为 0，否则会干扰结果。通常做法是将所有非有效状态初始化为无穷大（INT_MAX），然后单独处理第一行。
4. 优化技巧：为了统一处理左右边界的越界情况，可以将 DP 表多开两列（左右各一列），并全部初始化为 INT_MAX。这样在访问 j-1 或 j+1 时，如果是边界外，取到的就是无穷大，不会影响最小值的选择。

代码实现：

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，作为起始点
        // 这里利用 dp[0][...] = 0 的特性，配合循环从 1 开始计算
        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 minPrev = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]});
                dp[i][j] = minPrev + matrix[i - 1][j - 1];
            }
        }

        // 最后一行中的最小值即为答案
        int result = INT_MAX;
        for (int j = 1; j <= n; ++j) {
            result = min(result, dp[n][j]);
        }
        return result;
    }
};

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[0][1] 和 dp[1][0] 设为 0，其余设为 INT_MAX。这样在计算第一个实际元素 dp[1][1] 时，能正确取到 0 加上当前值。

代码实现：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 多开一行一列，初始化为 INT_MAX
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        
        // 设置虚拟起点，使得第一行和第一列能正常推导
        dp[0][1] = 0;
        dp[1][0] = 0;

        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];
    }
};

6. 地下城游戏

题目描述： 骑士需要从左上角出发，到达右下角拯救公主。每个房间可能扣血或回血。骑士在任何时刻生命值必须大于 0。求骑士出发时的最低初始健康点数。

思路分析： 这是一道经典的逆向思维 DP 题。如果正向思考（从起点到终点），我们无法确定到达某一点需要多少血量，因为这取决于后续路径的消耗。例如，前面血很多，后面坑很深，可能需要更多初始血量；反之亦然。因此，我们需要从终点倒推回起点。

1. 状态定义：dp[i][j] 表示从 (i, j) 位置出发到达终点所需的最低初始健康点数。
2. 转移方程：
   • 假设从 (i, j) 出发，下一步去右边或下边。我们需要保证到达下一个位置后，剩余血量至少为 1（即 dp[next]）。
   • 所以：dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]。
   • 如果计算结果为负数，说明当前房间回血足够多，甚至不需要额外血量就能维持生存，此时最低血量应为 1（不能小于 1）。
   • 修正公式：dp[i][j] = max(1, min(...) - dungeon[i][j])。
3. 初始化：
   • 终点 (n-1, m-1)：如果 dungeon 是负数（扣血），需要 1 - dungeon；如果是正数（回血），只需要 1。可以统一用 max(1, 1 - dungeon[n-1][m-1])。
   • 为了方便处理边界，DP 表同样多开一行一列，并将右下角的右侧和下侧邻居初始化为 1，代表到达终点后还需要 1 点血。
4. 遍历顺序：从下往上，从右往左。

代码实现：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        
        // 多开一行一列，初始化为 INT_MAX
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        
        // 初始化终点后的状态，表示到达终点后至少需要 1 点血
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                // 取右边和下边的最小需求
                int minNeed = min(dp[i + 1][j], dp[i][j + 1]);
                // 计算当前位置所需血量：minNeed - 当前房间值
                dp[i][j] = minNeed - dungeon[i][j];
                // 保证血量至少为 1
                dp[i][j] = max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

总结

二维动态规划的核心在于如何定义状态以及如何处理边界条件。

1. 状态定义：明确 dp[i][j] 的含义，是路径数、最大值还是最小代价？
2. 转移方程：根据题目允许的移动方向（上下左右或对角线）列出递推式。
3. 边界处理：善用'虚拟行/列'技巧，可以减少大量的 if 判断，让代码更简洁。
4. 遍历顺序：确保计算当前状态时，依赖的前置状态已经计算完成。对于依赖未来的问题（如地下城游戏），需采用逆序遍历。

掌握这些模式后，面对类似的网格 DP 问题，便能快速构建解题框架。