Python DP solution with comments


  • 1
    A
    class Solution:
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            # As moves possible are down and right then we need to calcualte next position value by adding left + up ( as this position can be             reached by either from left or from top). You know what we already know up and left value which are nothing but paths to reach them
            # go iteratively from start to end by 1 index 
            if(m == 0 or n == 0):
                return 0
            if(m == 1 or n == 1):
                return 1
            memo = [[0]*n for elem in range(m)]
            # Assign 1 to first row as there is no up hence it will be 1 only that is from left
            for j in range(n):
                memo[0][j] = 1
            # Assign 1 to first column as there is no left hence it will be 1 only that is from top
            for i in range(m):
                memo[i][0] = 1
            # Now for rest it is just left + top
            for i in range(1,m):
                for j in range(1,n):
                    memo[i][j] = memo[i-1][j]+memo[i][j-1]
            # Practically you have calculated maximum paths to reach each and every index 
            return(memo[-1][-1])
    

  • 0
    W

    It could be further simplified if we set memo = [[1]*n for _ in xrange(m)]
    The complete code is then shrunk to

    class Solution:
        def uniquePaths(self,m,n):
            memo = [[1]*n for _ in xrange(m)]
            for i in xrange(1,m):
                for j in xrange(1,n):
                    memo[i][j] = memo[i-1][j]+memo[i][j-1]
            return memo[-1][-1]
    

    All the test cases passed.


Log in to reply
 

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