[Leetcode]@python 62. Unique Paths

时间：2016-01-07 16:35:50 收藏：0 阅读：319

题目链接：https://leetcode.com/problems/unique-paths/

题目大意：给定n、m，在mxn的矩阵中，从（0，0）走到（m-1,n-1）一共有多少种法（只能往下和往右走）

解题思路：从（0，0）到（m-1,n-1）一共要走m - 1次向下，n-1次向右。也就是在n + m - 2次中选出m-1次向下，也就是C（m + n - 2,m-1）

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        ans = 1
        tmp = 1
        m -= 1;
        n -= 1
        k = min(n, m)
        i = 0
        while i < k:
            ans *= (m + n - i)
            tmp *= (k - i)
            i += 1

        return ans / tmp

View Code

原文：http://www.cnblogs.com/slurm/p/5110124.html