描述
在一个 m x n 的网格里，机器人位于 1 x 1 的位置，它最终要达到 m x n 的位置，每次只能向下或向右移动一格，问一共有多少种不同的走法。
样例
样例11
2输入: 7 3
输出: 28
样例21
2输入: 36 7
输出: 4496388
思路
- 动态规划 dp[i][j] = dp[i-1][j] + dp[i][j-1] 注意第一行和第一列都为1
- 直接计算，这是一个排列问题。 一共要向下走 m-1 步，向右走 n-1 步，只是考虑顺序问题，原问题转化为 (m-1)个白球 和 (n-1)个黑球排序，有多少种不同排法。这种方法要考虑溢出的问题。 计算公式为
(m+n-2)! /((m-1)! * (n-1)!)
代码
直接计算1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//(m+n-2)! / ((m-1)! * (n-1)!)
class Solution {
public:
int uniquePaths(int m, int n) {
m--,n--;
int bigger = m > n?m:n;
int small = m <= n?m:n;
long long res = 1;
for(int i=bigger+1;i<= bigger+small;i++){
res *= i;
}
// cout << res <<endl;
long long temp = 1;
for(int i=1;i<=small;i++){
temp *= i;
}
return res / temp;
}
};
dp1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,1));
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};