1. 动态规划

• 到达每个位置的路径数 = 到达该位置左边的路径数 + 到达该位置上边的路径数。
• 显然，第一行每个位置只有一条路径到达（只能向右），第一列的每个位置只有一条路径到达（只能向下）。
• 题目中m×n，m表示列，n表示行。双重循环行优先遍历。

class Solution {
public:int uniquePaths(int m, int n) {if(m==0 || n==0)    return 0;//m列n行vector<vector<int>> dp(n, vector<int>(m));for(int i=0; i<m; ++i){dp[0][i] = 1;}for(int j=0; j<n; ++j){dp[j][0] = 1;}for(int j=1; j<n; ++j){for(int i=1; i<m; ++i){dp[j][i] = dp[j][i-1] + dp[j-1][i];}}return dp[n-1][m-1];}
};

2. 排列组合

对于$m\times n$的网格，每次需要向右走$m-1$步，需要向下走$n-1$步，一共$m+n-2$步，所以不同路径的种数为：$C_{m+n-2}^{m-1}$

class Solution {
public：int uniquePaths(int m, int n) {//从m+n-2步中选择m-1步向右long long ans=1;for(int i=0;i<min(m-1,n-1);i++){            ans*=m+n-2-i;ans/=i+1;           }return (int)ans;}
}