Leetcode 62 Unique Paths in C [C語言]
==
###### tags: `Leetcode` `DP`

## Description
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.


## Exapmles
example1:

Input: m = 3, n = 7
Output: 28

example2:

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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

## 思路
最簡單的方式可以用 $$\frac{(m+n-2)!}{(m-1)!\times(n-1)!}$$
但是在執行Factorial 很容易overflow，而且時間上也沒有比較快，所以我認為直接用DP會是相對好的解決辦法。

可以看這圖，所有的m都是由m=2所組成的。他們之間的關係式很明顯(但是要全列出來我才看到...)

先把他用成小小一格一格來看，就算有多m,n有多大，都是由這些小格子所衍生而成。
這時候看到有多格的話就可以用recursive或是DP，感覺很多重複的子為題用DP會很快，這題目也很好整理。
以 m=3, n=7為例子：
有-的那一排一定只有一種可能所以可以先排除，剩下的問題可以用(m=2, n=7當做基底跑DP)

| - |- |- |- |- |- |- |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | | -|
| | | | | | | -|

## 程式

int uniquePaths(int m, int n){
    if(m==1 || n==1)    return 1;
    int tmp[n];
    for(int i=0; i<n; i++){
        tmp[i]=i+1;
    }
    for(int i=0; i<m-2; i++){    //(m-2)->最上面那一排不用算
        // 因為只有一種可能
        for(int j=1; j<n; j++){
            tmp[j]=tmp[j]+tmp[j-1];
        }
    }
    return tmp[n-1];
}