不同路径C++

以下是使用动态规划解决不同路径问题的 C++ 代码示例：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 初始化第一行和第一列的值为 1
        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];
    }
};

解释：

1. 定义一个二维数组 `dp` 用来记录到达每个点的不同路径数，其中 `dp[i][j]` 表示到达第 `i` 行第 `j` 列的位置的不同路径数。

2. 初始化二维数组 `dp`，将其第一行和第一列的值全部初始化为 1，因为到达第一行或第一列的任意位置只有一条路径。

3. 从第二行和第二列开始，使用动态规划的思想计算到达每个位置的不同路径数。具体地，到达当前位置的不同路径数等于到达上方位置和左侧位置的路径数之和。

4. 最后返回 `dp[m-1][n-1]`，即到达右下角位置的不同路径数。

以上代码使用动态规划的方式解决不同路径问题，时间复杂度为 $O(mn)$，适用于大规模问题。