目录

1  多维动态规划

2  62. 不同路径

3  64. 最小路径和

---

菜鸟做题，语言是 C++（细品动态规划 ing）

1  多维动态规划

目前的感觉：抽象为二维数组。

2  62. 不同路径

题眼：“机器人每次只能向下或者向右移动一步”。

核心思想：把总问题拆解为若干子问题。

• 总问题：到第 i 行第 j 列有多少条路径
• 子问题：到第 i - 1 行第 j 列有多少条路径、到第 i 行第 j - 1 列有多少条路径
• 总问题 = 子问题 1 + 子问题 2

思路说明图：如下图所示，到第 1 行第 2 列的路径数 = 到第 0 行第 2 列的路径数 + 到第 1 行第 1 列的路径数。此外，我们还需要设置边界路径数为 1，因为到达这些格子的路径只有 1 条。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));

        // 设置边界
        for (int i = 0; i < m; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 1;
        }

        // 计算路径
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

设置边界主要就是为了防止 dp[i - 1][j] 和 dp[i][j - 1] 访问越界。

3  64. 最小路径和

题眼：“每次只能向下或者向右移动一步”。

核心思想：把总问题拆解为若干子问题。

• 总问题：到第 i 行第 j 列的路径和
• 子问题：到第 i - 1 行第 j 列的路径和、到第 i 行第 j - 1 列的路径和
• 总问题 = 子问题 1 + 子问题 2

思路说明图：如下图所示，本题的边界初始化与  62. 不同路径  略有不同。

本质上就是把边界格子的路径和预先算出来。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n));

        // 设置边界
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; ++i) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < n; ++j) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        // 计算路径和
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }
};