Python dp solution with explanation


  • 0
    A

    The idea is to initialize the first row and col with value 1, since the robot is only allowed to move right or down. So there is only 1 way to get to positions in the first row or column.

    Then for a subsequent position dp[i][j], there are dp[i-1][j] plus dp[i][j-1] ways to get there.

     class Solution:
            # @return an integer
            def uniquePaths(self, m, n):
                dp = [[1 for i in range(m)] for i in range(n)]
                for col in range(m):
                    dp[0][i] = 1
                for row in range(n):
                    dp[row][0] = 1
                for row in range(1, n):
                    for col in range(1, m):
                        dp[row][col] = dp[row-1][col] + dp[row][col-1]
                return dp[-1][-1]

Log in to reply
 

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