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

3. 珠宝的最高价值

题目描述： 在一个矩阵中从左上角走到右下角，收集路径上的珠宝，求最大价值。

分析：

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 即可。

代码实现：

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

题目描述： 从第一行任意元素开始，每次移动到下一行的相邻元素，求路径和的最小值。

分析：

1. 状态表示：dp[i][j] 表示到达 (i, j) 的最小下降路径和。
2. 状态转移方程：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1]。
3. 初始化：由于求最小值，边界需初始化为正无穷大，防止越界影响结果。第一行直接取矩阵值。

代码实现：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        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[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] = 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. 地下城游戏

题目描述： 骑士需要从左上角出发到达右下角拯救公主，每一步生命值会增减。求初始最低健康点数。

分析： 此题无法正向推导，因为后续状态会影响当前所需血量。需采用逆向思维。

1. 状态表示：dp[i][j] 表示从 (i, j) 出发到达终点所需的最低初始健康点数。
2. 状态转移方程：dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]。
3. 细节处理：若计算结果为负数或 0，说明当前房间回血过多，只需保留 1 点血量即可，故取 max(1, result)。
4. 填表顺序：从下往上，从右往左。

代码实现：

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));
        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--) {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

总结

1. 状态定义：根据题目特性选择正向（从起点到当前）或逆向（从当前到终点）。
2. 边界处理：利用虚拟行列简化边界判断。
3. 初始化：注意求最大值时初始化为 0，求最小值时初始化为无穷大。
4. 填表顺序：确保计算当前状态时，依赖的状态已计算完成。