Python solutions with Math and DP O(m*n) o(m*n)


  • 0
    T

    This issue is straightforward with math.

    class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            res=1
            for i in range(1,m):
            	res=res*(m+n-1-i)/i
            return res
    

    However the math way may not help in question unique-paths-ii. Hence come up with below solution:P
    The unique path of each node (i,j) can be calculated by adding up the path to (i-1,j) and (i,j-1) when (i!=0 and j!=0)

    class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            #init
            tmp=[0 for i in range(n)]
            res=[tmp[:] for i in range(m)]
            res[0][0]=1
            for i in range(m):
            	for j in range(n):
            		if i==0 or j==0:
            			res[i][j]=res[0][0]
            		else:
            			res[i][j]=res[i-1][j]+res[i][j-1]
            return res[-1][-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.