# 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int m = 3;
int n = 7;
int res;
res = sol.uniquePaths(m, n);
cout << res;
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
int uniquePaths(int m, int n)
{
vector> path(m, vector(n, 0));
for (int i = 0; i < n; i++)
path[0][i] = 1;
for (int i = 0; i < m; i++)
path[i][0] = 1;
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
path[j][i] = path[j - 1][i + 1] + path[j + 1][i - 1];
return path[m - 1][n - 1];
}
};
```
## 选项
### A
```cpp
typedef vector BigInt;
class Solution
{
public:
int uniquePaths(int m, int n)
{
if (m == 0 || n == 0)
return 0;
if (m == 1 || n == 1)
return 1;
int m_ = m - 1 + n - 1;
int n_ = n - 1;
BigInt a = fac(m_);
int result = 0;
for (int i = n_; i >= 1; i--)
a = div(a, i);
for (int i = m_ - n_; i >= 1; i--)
a = div(a, i);
int k = a.size() - 1;
while (a[k] == 0)
k--;
for (int i = k; i >= 0; i--)
result = result * 10 + a[i];
return result;
}
BigInt fac(int n)
{
BigInt result;
result.push_back(1);
for (int factor = 1; factor <= n; ++factor)
{
long long carry = 0;
for (auto &item : result)
{
long long product = item * factor + carry;
item = product % 10;
carry = product / 10;
}
if (carry > 0)
{
while (carry > 0)
{
result.push_back(carry % 10);
carry /= 10;
}
}
}
return result;
}
BigInt div(BigInt a, int d)
{
int b = 0;
BigInt result;
int len = a.size();
for (int i = len - 1; i >= 0; i--)
{
b = b * 10 + a[i];
result.insert(result.begin(), b / d);
b = b % d;
}
return result;
}
};
```
### B
```cpp
class Solution
{
public:
int uniquePaths(int m, int n)
{
if (m <= 0 || n <= 0)
{
return 0;
}
vector> dp(m + 1, vector(n + 1, 0));
for (int i = 0; i < m; i++)
{
dp[i][0] = 1;
}
for (int i = 0; i < n; i++)
{
dp[0][i] = 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];
}
};
```
### C
```cpp
class Solution
{
public:
int uniquePaths(int m, int n)
{
int N = m + n - 2;
int M = m < n ? m - 1 : n - 1;
long ans = 1;
for (int i = 1; i <= M; i++)
ans = ans * (N - i + 1) / i;
return ans;
}
};
```