# 【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。


## 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

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++`