/**
1. dp:
1.1 状态定义: f[i][j]为达到 i,j 格子的路径数
1.2 状态计算: f[i][j] = f[i-1][j] + f[i][j-1];
1.3 边界: f[0][0] = 1;


2.排列组合:
2.1 无论怎么走, 一定会向右m-1步, 向左n-1步, 所以组合数为combo(m-1+n-1, n-1) 或 combo(m+n-2, m-1)
2.2  用long保存, 不然爆int
*/


class Solution {
    public int uniquePaths(int m, int n) {
        return combo(m+n-2,n-1);
        // return combo(m+n-2,m-1);
        // return dp(m,n);
    }

    public int combo(int x, int y){
        long res = 1;
        for (int i = 1; i <= y ; i++) res = res * (x-y+i) / i;
        return (int)res;
    }

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