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

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

绪论

本章聚焦二维动态规划。相比一维，状态表示从单点扩展为坐标 (x, y)，管理的维度增加，但核心逻辑一致：状态定义、转移方程、初始化、遍历顺序、结果返回。

若对动规基础尚不熟悉，建议先复习一维 DP 的五步分析法。这里我们直接应用这套思维模型，通过六个经典案例深入理解二维网格中的路径问题。

---

路径问题实战

1. 不同路径

题目描述： 机器人位于 m x n 网格左上角，每次只能向右或向下移动，求到达右下角的不同路径数。

思路分析：

• 状态定义： dp[i][j] 表示到达位置 (i, j) 的路径总数。
• 转移方程： 只能从上方或左方过来，故 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
• 初始化技巧： 为避免边界判断，通常给 DP 表多开一行一列。将 dp[0][1] 设为 1，这样第一行和第一列在计算时会自动累加为 1，符合题意（边缘只有一种走法）。
• 遍历顺序： 从上到下，从左到右。

class Solution {
public:
    int uniquePaths(int n, int m) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[0][1] = 1; // 虚拟节点初始化
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n][m];
    }
};

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

题目描述： 网格中存在障碍物，路径不能经过障碍物。

思路分析：

• 核心逻辑同上，只需增加障碍物判断。
• 遇到障碍物时，该位置路径数为 0，且不影响后续计算（因为 continue 跳过赋值，保持默认 0）。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        dp[0][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n][m];
    }
};

3. 珠宝的最高价值

题目描述： 从左上角走到右下角，收集路径上最大价值的珠宝。

思路分析：

• 状态定义： dp[i][j] 表示到达 (i, j) 时的最大价值。
• 转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1]。
• 初始化： 由于是求最大值，且边缘位置价值为 0，直接初始化为 0 即可，无需特殊处理。

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n = frame.size(), m = frame[0].size();
        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. 下降路径最小和

题目描述： 从第一行任意元素出发，每次可移动到下一行的左下、正下、右下，求最小路径和。

思路分析：

• 难点： 涉及三个方向，且需处理边界越界问题。
• 初始化陷阱： 求最小值时，未访问状态应初始化为无穷大 (INT_MAX)，防止被误选。
• 优化： 同样采用多开行列的方式简化边界判断，将第一行初始化为 0，其余为 INT_MAX。

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. 最小路径和

题目描述： 从左上角到右下角，路径数字之和最小。

思路分析：

• 与'不同路径'类似，只是将加法改为求和取最小。
• 初始化技巧：利用 dp[0][1] 和 dp[1][0] 为 0 的特性，配合 INT_MAX 填充，自动处理第一行和第一列的累加。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[0][1] = 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. 地下城游戏

题目描述： 骑士从左上角出发，到达右下角拯救公主，途中血量不能低于 1，求初始最低健康点数。

思路分析：

• 逆向思维： 正向推导困难，因为当前血量需求取决于未来路径的消耗。因此需从终点 (n-1, m-1) 反向推导至起点 (0, 0)。
• 状态定义： dp[i][j] 表示从 (i, j) 出发到达终点所需的最小初始健康值。
• 转移方程： dp[i][j] = min(右边，下边) - dungeon[i][j]。
• 边界处理： 若计算结果为负数，说明当前位置收益足够覆盖后续消耗，但健康值至少为 1，故取 max(1, 计算值)。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        // 终点后方的虚拟节点设为 1，保证终点计算正确
        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] = max(minNeed - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

---

总结

二维 DP 的核心在于状态定义的准确性。对于路径计数类问题，通常正向递推；对于涉及资源消耗或依赖未来状态的问题（如地下城），尝试逆向思考往往能化繁为简。此外，善用虚拟行/列进行边界保护，能让代码更简洁健壮。