LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Unique Paths

2d-dp unique-paths

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Examples

Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 2
Output: 3
Key Insight

To reach cell (i,j), you either came from (i-1,j) or (i,j-1).

dp[i][j] = dp[i-1][j] + dp[i][j-1]. First row and column are all 1s. Or use combinatorics: C(m+n-2, m-1).

How to Approach This Problem

Pattern Recognition: When you see keywords like unique paths 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 To reach cell (i, j), you came from:
Answer: (i-1, j) or (i, j-1)
Can only move right or down. So you arrived from above or from left.
2 dp[i][j] = ?
Answer: dp[i-1][j] + dp[i][j-1]
Total ways = ways from top + ways from left.
3 For cells in the first row (i=0):
Answer: dp[0][j] = 1
Only one way to reach any cell in first row: keep going right.
4 For cells in the first column (j=0):
Answer: dp[i][0] = 1
Only one way to reach any cell in first column: keep going down.
5 We can reduce space to O(n) because:
Answer: We only need the previous row
Each row only depends on the row above it.

Solution

def uniquePaths(m: int, n: int) -> int:
    # Space-optimized 1D DP
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    
    return dp[n - 1]

Complexity Analysis

Time O(m × n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye