[数据结构与算法]LeetCode 62.不同路径(动态规划/组合数）

题目描述：（来自LeetCode官网）

?

1.用动态规划求解?

思路：从左上角走到右下角，每一次可以选择向下走或者向右走。用dp[i][j]表示走第i行第j列这个格子的路径数，而走到这个各自可能是从上面走过来的也可能是从下面走过来的，那么走到这一步的路径数就是dp[i-1][j]和dp[i][j-1]的路径数的和，但是，有两种特殊情况，就是在第一行或者第一列的格子，我们都只有一种可能到达的路径，让dp[0][j]和dp[i][0]等于1就是，

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[105][105];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){//特殊情况，在第一列的话，到达第i行只能是从上面下来的，在第一行的话，走到第j列，只能是从左侧走过来的。
                    dp[i][j]=1;
                }else{//其他格子都有两种情况
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

2.用组合数求解

还有一种很妙的方法，我们可以发现，无论怎么走，从左上角到右下角都需要走m+n-2步，而且，往右走的步数一定是n-1,往下走的步数一定是m-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;y++,x++){
            ans=ans*x/y;
        }
        return ans;
    }
};

今日刷题任务完成，不过纯纯照搬题解，想不出来，我真蠢，明天见~。