[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

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!