【leetcode刷题】20T28-不同路径

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 排列组合问题
        # 实际上，向下走m-1步，向右走n-1步
        # (m+n-2)! / ((m-1)! * (n-1)!)
        res = 1
        for i in range(m, m + n - 1):
            res *= i
        for i in range(1, n):
            res /= i
        return res

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 总步数 m+n-2
        double res = 1;
        if(m < n){
            int tmp = m;
            m = n;
            n = tmp;
        }
        for(int i=m, j=1; i<m+n-1; i++, j++){
            res *= i;
            if(j < n)
                res /= j;
        }
        return res;
    }
};