Question: https://oj.leetcode.com/problems/unique-paths/
Question Name: Unique Paths
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: # @return an integer def uniquePaths(self, m, n): # From the top-left cell to bottom-right cell, there are # totally m+n-2 moves. Among these moves, m-1 is moving # downwards, and n-1 is moving to right. So the number of # possible unique paths = C(m+n-2, m-1) = C(m+n-2, n-1). result = 1 # Because C(m+n-2, m-1) = C(m+n-2, n-1), we are going to # do one with less steps. total = m + n - 2 chosen = min(m, n) - 1 # http://en.wikipedia.org/wiki/Binomial_coefficient for i in xrange(total, total-chosen, -1): result *= i for i in xrange(chosen): result //= (i+1) return result |