---
# System prepended metadata

title: 'Leetcode 62 Unique Paths in C [C語言]'
tags: [Leetcode, DP]

---

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.

 ![](https://i.imgur.com/wA5HIJT.png)

## 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會是相對好的解決辦法。

![](https://i.imgur.com/cUYG7Nk.jpg)
可以看這圖，所有的m都是由m=2所組成的。他們之間的關係式很明顯(但是要全列出來我才看到...)

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


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


## 程式
```c=
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];
}
```
![](https://i.imgur.com/QtpDe75.png)
