Unique Paths

Dynamic Programming2D Matrix

20 min

Problem Statement

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?

Example

Example 1:

m = 3, n = 7

Output: 28

Solution

This problem can be solved using dynamic programming. We can create a 2D DP grid of the same size as the input grid, where `dp[i][j]` stores the number of unique paths to reach cell `(i, j)`.

The number of ways to reach any cell `(i, j)` is the sum of the ways to reach the cell above it (`i-1, j`) and the cell to its left (`i, j-1`). The base cases are the cells in the first row and first column, which can only be reached in one way.

Algorithm Steps (DP)

Create an `m x n` DP grid initialized with 0s.
Initialize the first row and first column to 1, as there's only one way to reach each of these cells.
Iterate through the rest of the grid, starting from `(1, 1)`.
For each cell `(i, j)`, calculate `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
The final answer is the value in the bottom-right cell, `dp[m-1][n-1]`.

Unique Paths DP Grid

Progress1 / 1

Ready to start.

Unique Paths (DP)


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Create a 2D DP grid
        dp = [[0] * n for _ in range(m)]
        
        # Initialize the first row and column to 1
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
            
        # Fill the rest of the grid
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
        return dp[m-1][n-1]