动态规划

• 思路：
  • 定义 dp[r][c] 为到达坐标 (r, c) 的路径数：
    • 它只能有同一行左边相邻方格向右到达或者同一列上方相邻方格向下到达；
  • 状态转移方程：
    • dp[r][c] = dp[r][c - 1] + dp[r - 1][c]
  • 初始状态
    • dp[0][0] = 1
    • 第一行的路径数是 1
    • 第一列的路径数是 1
  • 动态规划求出所有 dp 数组的路径数，结果为 dp[m - 1][n - 1]；

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 1;
        }

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

        dp[0][0] = 1;
        for (int c = 1; c < n; ++c) {
            dp[0][c] = 1;
        }
        for (int r = 1; r < m; ++r) {
            dp[r][0] = 1;
        }

        for (int r = 1; r < m; ++r) {
            for (int c = 1; c < n; ++c) {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
            }
        }

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

——————————————————————————————————