Unique Paths

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there? Tags: Dynamic Programming

Try It!

Discussion

Video

Solution

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for c in range(n)] for r in range(m)]
        
        for r in range(m):
            dp[r][0] = 1
        for c in range(n):
            dp[0][c] = 1
        
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] += dp[r - 1][c] + dp[r][c - 1]

        return dp[m - 1][n - 1]