不同路径

不同路径

思路：

法一：动态规划

    const int N = 110;
class Solution {    int dp[N][N];//dp[i][j]：从起点走到 i j的路径个数。 public:int uniquePaths(int m, int n) {for(int i=1;i<=n;i++){dp[1][i]=1;} for(int i=1;i<=m;i++) dp[i][1]=1;for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};

滚动数组：

    const int N = 110;
class Solution {    int dp[N];//dp[i][j]：从起点走到 i j的路径个数。 public:int uniquePaths(int m, int n) {for(int i=1;i<=n;i++){dp[i]=1;} for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){dp[j]+=dp[j-1];}}return dp[n];}
};

法二：组合数学

        从左上角到右下角的过程中，我们需要移动 m+n−2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数

class Solution {
public:int uniquePaths(int m, int n) {long long ans = 1;for (int x = n, y = 1; y < m; ++x, ++y) {ans = ans * x / y;}return ans;}
};