Python DP Solution with explaination


  • 0
    class Solution(object):
        def uniquePaths(self, m, n):
            # m = rows, n = cols
            dp = [[0 for i in range(n)] for j in range(m)]
            # set final block to be one
            dp[m-1][n-1] = 1
            # set bottom row to be all equal to 1
            for i in range(n):
                dp[m-1][i] = 1
            # set right most col ro be all equal to 1
            for i in range(m):
                dp[i][n-1] = 1
            # fill out rest of dp array
            for i in range(m-2, -1, -1):
                for j in range(n-2, -1, -1):
                    dp[i][j] = dp[i+1][j] + dp[i][j+1]
            return dp[0][0]
    

Log in to reply
 

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