# The Number of Unique Paths in a Grid (Python)

You’re given a 2D grid or array. The goal is to determine the number of unique paths from the top-left corner of this grid to the bottom-right corner. You can only move either right or down.

Consider a 5x5 grid as shown in the given figure. You start at the top-left corner and want to reach the bottom-right corner. If you take only right moves, you’d trace one possible path. If you take only down moves first and then move right, you’d trace another path. The problem is to find how many such paths exist.

## Brute Force Approach

Enumerate all possible paths from the top-left to the bottom-right using recursion. However, this approach is highly inefficient due to a large number of possible paths (combinatorial explosion). With this approach, you might end up computing paths for the same cells multiple times.

## Optimized Approach

We can improve the brute force approach by using Dynamic Programming.

The core idea is to compute the number of ways to get to a cell `(i, j)`

by using the results from its neighboring cells.

The number of ways to get to a cell `(i, j)`

is the sum of:

- Number of ways to get to the cell above it
`(i-1, j)`

- Number of ways to get to the cell to its left
`(i, j-1)`

```
def count_unique_paths(n, m):
# Create a cache for memoization to avoid recalculating paths
paths_cache = [[0] * m for _ in range(n)]
# Define the recursive function to compute number of paths to (x, y)
def compute_paths_to_xy(x, y):
if x == y == 0:
return 1
if paths_cache[x][y] == 0:
ways_top = 0 if x == 0 else compute_paths_to_xy(x - 1, y)
ways_left = 0 if y == 0 else compute_paths_to_xy(x, y - 1)
paths_cache[x][y] = ways_top + ways_left
return paths_cache[x][y]
# Calculate the number of paths to the bottom-right corner
return compute_paths_to_xy(n - 1, m - 1)
```

In Python, nested functions have access to the variables defined in their enclosing scope. This feature is known as a “closure”, which means that the inner function `compute_paths_to_xy(x, y)`

remembers the variables from its enclosing scope `count_unique_paths(n, m)`

, even if that scope is no longer executing.

The dynamic programming approach you’ve outlined is already quite efficient for solving this problem as it ensures that each subproblem is only solved once. However, we can still make a slight improvement by using an **iterative approach **instead of a recursive one. The iterative approach uses a bottom-up method and typically runs a bit faster because it doesn’t have the overhead of the call stack that recursive functions incur.

Here is the iterative version of the dynamic programming solution:

```
def count_unique_paths(n, m):
# Initialize a 2D list with 1's as there is 1 way to reach any cell in the first row or column
paths_cache = [[1] * m for _ in range(n)]
# Start from cell (1, 1) as the first row and column are already initialized
for i in range(1, n):
for j in range(1, m):
# The number of paths to current cell is the sum of the paths
# from the cell above it and the cell to the left of it
paths_cache[i][j] = paths_cache[i - 1][j] + paths_cache[i][j - 1]
# The bottom-right corner will contain the total number of unique paths
return paths_cache[-1][-1]
```

This code will compute the same results as the recursive approach but does so iteratively by filling in the grid from top to bottom, left to right. After filling in the grid, `paths_cache[-1][-1]`

will contain the total number of unique paths from the top-left to the bottom-right.

Another even more efficient solution would be to use a single array instead of a 2D array since we only need the current and previous rows to compute the number of paths:

```
def count_unique_paths(n, m):
# Initialize a list with 1's as there is 1 way to reach any cell in the first row
paths = [1] * m
# Iterate through rows starting from the second one
for i in range(1, n):
for j in range(1, m):
# The value of paths[j] is updated to paths[j] (from left cell) + paths[j-1] (from top cell)
paths[j] += paths[j - 1]
# The last element will contain the total number of unique paths
return paths[-1]
```

This final optimization reduces the space complexity from O(n*m) to O(m) and still maintains the time complexity of O(n*m).

*Subscribe to my newsletter** to get access to all the content I’ll be publishing in the future.*