題目：
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）缅叠。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）珠漂。
問總共有多少條不同的路徑页徐？
例如愈案，上圖是一個(gè)7 x 3 的網(wǎng)格。有多少可能的路徑返顺？
說明：m 和 n 的值均不超過 100禀苦。
示例 1:
輸入: m = 3, n = 2
輸出: 3
示例 2:
輸入: m = 7, n = 3
輸出: 28
方法一：動(dòng)態(tài)規(guī)劃
思路：
1、令 dp[i][j] 是到達(dá) i, j 最多路徑
2遂鹊、機(jī)器人只能向右或向下移動(dòng)一步
（1）從左上角到右下角的走法 = 從右邊開始走的路徑總數(shù)+從下邊開始走的路徑總數(shù)
（2）即 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3振乏、初始化第一行和第一列的值，因?yàn)橐恢毕蛳禄蛘咭恢毕蛴易叨晦D(zhuǎn)向的話只有一種走法秉扑，所以慧邮，dp[0][j] = 1，dp[i][0] = 1
時(shí)間復(fù)雜度： O(m * n)
空間復(fù)雜度： O(m * n)
var uniquePaths = function(m, n) {
let dp = Array.from(new Array(n), () => new Array(m).fill(0));
for(let i = 0; i < m; i++){
dp[0][i] = 1;
}
for(let i = 0; i < n; i++){
dp[i][0] = 1;
}
for(let i = 1; i < n; i++){
for(let j = 1; j < m; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n - 1][m - 1];
};
方法二：排列組合
思路：
1舟陆、起點(diǎn)和終點(diǎn)不算在內(nèi)误澳，那總共走的步數(shù)為：N = m+n-2;
2、向下走的步數(shù)為：k = m -1
時(shí)間復(fù)雜度： O(m)
空間復(fù)雜度： O(1)
var uniquePaths = function(m, n) {
let N = n + m - 2;
let k = m - 1;
let result = 1;
for(let i = 1; i <= k; i++){
result = result * (N - k + i) / i
}
return result;
};
