Chapter 3: Navigating a Grid - Unique Paths

So far, our journey has taken us along one-dimensional paths: a staircase and a street of houses. Now, we will elevate our thinking to a second dimension. Many dynamic programming problems involve navigating a grid, and LeetCode's "Unique Paths" (Problem #62) is the quintessential example.

This problem will challenge us to adapt our (n-1) and (n-2) logic to a (row, col) coordinate system, but you will see that our core three-step framework holds up perfectly.

The Problem:

A robot is located at the top-left corner of an 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?

For example:

• For a 3 x 2 grid, there are 3 unique paths:

  1. Right -> Down -> Down

  2. Down -> Down -> Right

  3. Down -> Right -> Down

• For a 3 x 7 grid, the answer is 28.

Approach 1: The Recursive Solution

Let's think about how the robot can reach any given cell (row, col). Since it can only move down or right, it must have arrived at (row, col) from one of two possible cells:

1. The cell directly above it: (row - 1, col)

2. The cell directly to its left: (row, col - 1)

Therefore, the total number of unique paths to reach (row, col) is the sum of the paths to reach the cell above it and the paths to reach the cell to its left.

This gives us our recursive formula: paths(row, col) = paths(row - 1, col) + paths(row, col - 1)

What are our base cases?

• Any cell in the first row (row = 0) can only be reached from the left. There is only 1 way to get there.

• Any cell in the first column (col = 0) can only be reached from above. There is also only 1 way to get there.

Let's implement this.

def uniquePaths_recursive(m: int, n: int) -> int:
    def solve(row, col):
        # Base case: If we're in the first row or first column, there's only one path.
        if row == 0 or col == 0:
            return 1

        # Recursive step
        from_above = solve(row - 1, col)
        from_left = solve(row, col - 1)

        return from_above + from_left

    # Start from the bottom-right corner
    return solve(m - 1, n - 1)

# Trying it out
# print(uniquePaths_recursive(3, 7)) # Output: 28
# print(uniquePaths_recursive(23, 12)) # This will be EXTREMELY slow

As expected, this pure recursive approach is too slow for larger grids because it constantly re-calculates the paths for the same cells.

Approach 2: Memoization with a Decorator (Top-Down DP)

You know what to do. To fix the re-computation issue, we'll cache the results of our solve(row, col) function calls. A simple decorator will do the trick.

import functools

class Solution:
    def uniquePaths_memoized(self, m: int, n: int) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(row, col):
            if row == 0 or col == 0:
                return 1

            from_above = solve(row - 1, col)
            from_left = solve(row, col - 1)

            return from_above + from_left

        return solve(m - 1, n - 1)

# Trying it out
# solver = Solution()
# print(solver.uniquePaths_memoized(23, 12)) # Instantaneous!

The logic remains identical to our recursive solution, but the performance is now excellent. Top-down DP allows us to write code that mirrors our initial, intuitive thoughts while still being highly efficient.

Approach 3: Iteration (Bottom-Up DP)

Now, let's build the solution from the ground up. Instead of a couple of variables, we'll need a 2D array, often called a dp table, to store the number of paths to each cell.

1. Create an m x n grid (let's call it dp) and initialize all its values to 1.

2. Why 1? Because we know there is exactly one way to reach any cell in the first row (by only moving right) and one way to reach any cell in the first column (by only moving down). Our grid is pre-filled with the correct values for our base cases.

3. Now, we can iterate through the rest of the grid, starting from cell (1, 1).

4. For each cell dp[row][col], we'll apply our formula: dp[row][col] = dp[row - 1][col] + dp[row][col - 1].

The final answer will be the value in the bottom-right cell, dp[m-1][n-1].

def uniquePaths_iterative(m: int, n: int) -> int:
    # Create a 2D grid initialized with 1s
    dp = [[1 for _ in range(n)] for _ in range(m)]

    # Iterate through the grid, starting from (1, 1)
    for row in range(1, m):
        for col in range(1, n):
            # The number of paths to the current cell is the sum of paths
            # from the cell above and the cell to the left.
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

    # The result is in the bottom-right cell
    return dp[m - 1][n - 1]

# Trying it out
# print(uniquePaths_iterative(23, 12)) # Also instantaneous and very clear

This bottom-up approach is clean, efficient, and often easier to debug than recursion for grid problems. It has a time complexity of O(mn) and a space complexity of O(mn) to store the grid.

Conclusion

In this chapter, we successfully transitioned our dynamic programming skills from one dimension to two. We saw that while the data structure changed (from variables to a 2D array), the underlying principles did not. We still:

1. Defined a recursive relationship.

2. Optimized it with memoization.

3. Rebuilt it from the ground up with an iterative, tabulation-based approach.

You are now equipped to handle a large category of DP problems. In the next chapter, we'll add another twist to our grid problems.