Unique Paths | Leetcode 62 | All 4 DP Solutions

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.

Here’s the [Problem Link] to begin with.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

Solution 1: Brute Force Approach (Recursion)

Intuition

At any position (i, j), the robot considers moving up from (i-1, j) or left from (i, j-1) to reach (i, j). Base cases:

• If at (0, 0), it’s the starting point, one way found!
• If out of bounds (i < 0 or j < 0), it’s invalid—no way.

So we recursively sum the number of ways to reach the cell from above and left.

Detailed Approach

• Base: If i == 0 and j == 0, return 1 (starting cell).
• If out of bounds, return 0.
• Otherwise, return up + left, where up = solve(i-1, j), left = solve(i, j-1).

Code

class Solution:
    def solve(self, i, j, m, n):
        # At start cell: one way
        if i == 0 and j == 0:
            return 1
        # Out of bounds: no way
        if i < 0 or j < 0:
            return 0
        # Recursively sum from above and left
        up = self.solve(i - 1, j, m, n)
        left = self.solve(i, j - 1, m, n)
        return up + left

    def uniquePaths(self, m: int, n: int) -> int:
        # Start recursion from end point
        return self.solve(m - 1, n - 1, m, n)

Code Explanation

The function solve(i, j, m, n) finds the number of unique ways to reach (i, j) by stepping only up or left. The uniquePaths function kicks off solving from the bottom-right target.

Time & Space Complexity

• Time: O(2^(m*n)) (Exponential; explores all paths recursively)
• Space: O(m*n) (Maximum recursion stack)

Solution 2: Memoization (Top-Down DP)

Intuition

Recursive approach recalculates the same subproblems many times. Memoization uses a DP table to cache results for each (i, j), so every cell is only solved once.

Detailed Approach

• Use a 2D DP array initialized to -1.
• If a cell’s value is NOT -1, return it directly.
• Compute up + left for each cell (same recursion, but with DP).

Code

class Solution:
    def solve(self, i, j, m, n, dp):
        # Base case: Start cell
        if i == 0 and j == 0:
            return 1
        # Out of bounds
        if i < 0 or j < 0:
            return 0
        # Return from DP if already computed
        if dp[i][j] != -1:
            return dp[i][j]
        # Compute paths from up and left
        up = self.solve(i - 1, j, m, n, dp)
        left = self.solve(i, j - 1, m, n, dp)
        dp[i][j] = up + left
        return dp[i][j]

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[-1 for _ in range(n)] for _ in range(m)]
        return self.solve(m - 1, n - 1, m, n, dp)

Code Explanation

The memoized DP ensures each cell (i, j) is solved just once, drastically improving efficiency. If a subproblem is seen before, it’s reused.

Time & Space Complexity

• Time: O(m*n) (Each cell solved once)
• Space: O(m*n) (DP table + recursion stack)

Solution 3: Tabulation (Bottom-Up DP)

Intuition

Iteratively build the solution from (0, 0) to (m-1, n-1). At each cell (i, j), the number of unique paths to reach it is the sum of paths from above and from the left.

Detailed Approach

• Create DP table dp[m][n].
• dp = 1 (start point)
• For each cell:
  • If i == 0: only possible from the left
  • If j == 0: only possible from above
  • Else: sum of top and left cells
• Return dp[m-1][n-1].

Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # DP table for all cells
        dp = [[-1 for _ in range(n)] for _ in range(m)]
        dp[0][0] = 1  # Start position
        for i in range(0, m):
            for j in range(0, n):
                if i == 0 and j == 0:
                    continue
                # If no upper cell, up=0; else, up=dp[i-1][j]
                if i == 0:
                    up = 0
                else:
                    up = dp[i - 1][j]
                # If no left cell, left=0; else, left=dp[i][j-1]
                if j == 0:
                    left = 0
                else:
                    left = dp[i][j - 1]
                dp[i][j] = up + left
        return dp[m - 1][n - 1]

Code Explanation

Builds up the DP table row by row and fills each cell with the total paths from above and left cells, skirting recursion entirely.

Time & Space Complexity

• Time: O(m*n) (Each cell filled once)
• Space: O(m*n) (DP table)

Solution 4: Tabulation (Space Optimization)

Intuition

At any point, we only need the current and previous rows. Instead of using the entire dp matrix, keep just two 1D arrays: prev (previous row) and curr (current row).

Detailed Approach

• Initialize prev (previous row) of size n.
• For each row:
  • curr[j] is computed as sum of prev[j] (from above) and curr[j-1] (from left).
• After row is computed, set prev = curr.
• Return prev[n-1].

Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        prev = [-1] * n  # Previous row
        for i in range(0, m):
            curr = [-1] * n  # Current row
            for j in range(0, n):
                if i == 0 and j == 0:
                    curr[0] = 1  # Start
                    continue
                # up: from the row above
                if i == 0:
                    up = 0
                else:
                    up = prev[j]
                # left: from the same row, previous column
                if j == 0:
                    left = 0
                else:
                    left = curr[j - 1]
                curr[j] = up + left
            prev = curr  # Move current row to prev
        return prev[n - 1]

Code Explanation

Reduces space dramatically, only store one row at a time instead of the whole grid.

Time & Space Complexity

• Time: O(m*n) (Each cell)
• Space: O(1) (Only two row arrays)

Summary Table

Conclusion

The Unique Paths problem is a classic DP stepping stone. Start by building an intuition with brute force, then scale up through memoization, tabulation, and finally, space-optimized solutions!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.