This is a 2-d dynamic programming problem, but it follows the same method of solving we start with a recursive approach, memoize, and finally recognize the pattern to come up with a bottom-up iterative approach. If you looked at just the recursive approach it would be hard to tell this is a 2-d problem, it’s when you look at the iterative dp table that it makes a difference.

In this problem, you just have to pretty much traverse the matrix using depth-first search till you reach the end index, and you can only go in the bottom and right directions. This is a dp problem because you can cache ways you can get to the end from any other index in the grid. Ways to get to the end from a certain grid is just ways to get to the end from the bottom index + the ways to get to the end from the right index. And for any grid where the bottom or right index is out of bounds the ways to get there from that grid is 1. We use this idea to just fill out our dp table.

The time complexity of both approaches is O(nm), but the space complexity for the recursive approach is O(nm), while the space complexity for the iterative approach is O(n).

Recursive (Memoization) Approach

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # T: O(nm) S: O(nm)
        end = m-1, n-1
        memo = {end:1}
        def uP(r, c):
            if not (0<=r<m and 0<=c<n):
                return 0
            if (r, c) not in memo:
                memo[(r, c)] = uP(r, c+1) + uP(r+1, c)
            return memo[(r, c)]
        return uP(0, 0)

Iterative Approach

If we realize that we only need to look back in the previous row, we know that’s all we need to cache and we can optimize the space complexity to O(n).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # T: O(nm) S: O(n)
        dp = [1]*n
        for r in range(m-1):
            for c in reversed(range(n-1)):
                dp[c] += dp[c+1]
        return dp[0]