leetcode

Unique Paths

Unique Paths

Math Method

1
2
3
4
5
6
7
8
9
import math
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return math.factorial(m+n-2) / math.factorial(m-1) / math.factorial(n-1)

Write down your command in a sequence, “right, down, down, right, …” it will always be m+n-2 slots, u just need to insert n-1 “right” commands uniquely in this sequence,and that is just binomial coefficient of m+n-2 choose n-1.

DP Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        aux = [[1 for x in xrange(n)] for x in xrange(m)]
        #print aux
        for i in range(1, m):
            for j in range(1, n):
                aux[i][j] = aux[i][j-1] + aux[i-1][j]
        #print aux
        return aux[-1][-1]

test code

1
2
3
4
5
6
In [329]: s = Solution(); t = s.uniquePaths(3, 2)
[[1, 1], [1, 1], [1, 1]]
[[1, 1], [1, 2], [1, 3]]
In [330]: t
Out[330]: 3

leet code