# 【LeetCode】 62. Unique Paths
## Description
> A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
> The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
> How many possible unique paths are there?
> Note: m and n will be at most 100.
> 有一個機器人在一個m*n的網格裡的最左上角。
> 它每次只能往下或往右走一格,它的終點是最右下角。
> 它有幾種不同的路徑?
> 提示:m和n最多只有100。
![](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)
## Example:
```
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
```
## Solution
* 直接用數學解,排列組合問題。
* 它從起點到終點,總共需要`m-1`個往右,`n-1`個往下。
* 總共的排列數為$$\frac{(m-1 + n-1)!}{(m-1)!(n-1)!}$$
* 因為用到階層,記得使用`long long int`,否則會溢位。
### Code
```C++=1
class Solution {
public:
int uniquePaths(int m, int n) {
if(m<n) return uniquePaths(n,m);
m--;n--;
int temp = m+n;
long long int ans = 1;
for(int i = temp;i>m;i--)
ans*=i;
for(int i = 2;i<=n;i++)
ans/=i;
return ans;
}
};
```
###### tags: `LeetCode` `C++`