【LeetCode】0062 不同路径

https://leetcode-cn.com/problems/unique-paths/

# -*- coding:utf-8 -*-
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 1 or n == 1:
            return 1
        m = m - 1
        n = n - 1
        res = 1
        for i in range(m + n, m, -1):
            res *= i
        for i in range(1, n + 1):
            res /= i
        return int(res)
if __name__ == '__main__':
    m = 6
    n = 3
    print(Solution().uniquePaths(m, n))

思路：其中总计要有m+n-2条路径，其中有n-1条路径是向下的，因此实际上就是计算C_{n-1,m+n-c}即可。