Leetcode62. 不同路径

题目：

代码（首刷自解）：

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==1||n==1) return 1;
        // 1.dp[i][j]下标含义：达到dp[i][j]的路径总数
        vector<vector<int>> dp(m,vector<int>(n));
        // 2.初始化，第一行和第一列的格子都只有一种走法
        for(int i=1;i<m;++i) dp[i][0]=1;
        for(int j=1;j<n;++j) dp[0][j]=1;
        // 3.递推方向，从左到右，从上到下
        for(int i = 1;i < m ; ++i){
            for(int j = 1;j < n;++j){
                // 4.递推公式
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};