# 0062. Unique Paths
###### tags: `Leetcode` `Medium` `动态规划`
Link: https://leetcode.com/problems/unique-paths/

## 思路
两种方法
一个是用排列组合（还没理解）
一个是用动态规划，要注意的是这里不用建m*n的阵列，只要存一行的就好
## Code
### 方法一

### 方法二

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[n];
        for(int i = 0;i < m;i++){
            if(i == 0){
                for(int j = 0;j < n;j++){
                    dp[j] = 1;
                }
            }
            else{
                for(int j = 1;j < n;j++){
                    dp[j] = dp[j]+dp[j-1];
                }
            }
        }
        return dp[n-1];
    }
};

## Result
Runtime: 0 ms, faster than **100.00%** of C++ online submissions for Unique Paths.
Memory Usage: 5.8 MB, less than **86.65%** of C++ online submissions for Unique Paths.

## 思路in Java
### 方法一
可怜的我就是用的m*n的二维数组，不过我尝试想了能不能优化空间，没想出来。

那我再想想怎么只要存一行
#### 先来一个简略版的

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        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];
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.3 MB, 在所有 Java 提交中击败了49.37%的用户

#### 空间优化版
🐂啊这种优化，看着比较晕，但是手推一遍就懂里
相当于是每次更新一行

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    dp[j] = 1;
                }
            } else {
                for (int j = 1; j < n; j++) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：34.9 MB, 在所有 Java 提交中击败了96.79%的用户

## 方法二：排列组合
从左上角移动到右下角一共需要移动$m+n-2$次，其中$m-1$向下移动，$n-1$向右移动。那么总的路径数，就是从$m+n-2$次移动种挑出$m-1$个，也就是组合数$C_{m+n-2}^{m-1}$。

注意：$C_{m+n-2}^{m-1}=C_{m+n-2}^{n-1}=\frac{(m+n-2)!}{(m-1)!(n-1)!}$。

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}