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

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