< Back




62. Unique Paths

We're asked to find the number of unique paths from (0, 0) to (m - 1, n - 1) for a matrix with m
rows and n columns. We're only able to move in two directions, down and right. This is a common
dynamic programming problem, and we can solve and think of this problem like a graph.

Recursively, we know that at each step we have two choices, down or right. With that, we make both
choices, if possible, and recursively record the number of ways we can reach the bottom right
corner. Using the @cache feature for functools, we can avoid recalculating paths we've already
discovered.

Similarly, for the recursive function, we traverse the graph in reverse. We start at (m - 1, n - 1)
and make our way towards (0, 0). We reuse values of the table we've created to memoize our number of
paths. If we can't travel down and right, we reuse existing values. If we can, we add the results of
boths paths. Eventually, (0, 0) will contain the number of unique paths to reach (m - 1, n - 1).

The recursive solution is as follows:


  class Solution:
      def uniquePaths(self, m: int, n: int) -> int:
          @cache
          def dp(i: int, j: int) -> int:
              if i == m - 1 and j == n - 1:
                  return 1

              c = 0

              if i < m - 1:
                  c += dp(i + 1, j)

              if j < n - 1:
                  c += dp(i, j + 1)

              return c

          return dp(0, 0)


The iterative solution is as follows:


  class Solution:
      def uniquePaths(self, m: int, n: int) -> int:
          T = [[0 for _ in range(n)] for _ in range(m)]

          for i in range(m - 1, -1, -1):
              for j in range(n - 1, -1, -1):
                  if i == m - 1 and j == n - 1:
                      T[i][j] = 1
                  elif i == m - 1:
                      T[i][j] = T[i][j + 1]
                  elif j == n - 1:
                      T[i][j] = T[i + 1][j]
                  else:
                      T[i][j] = T[i + 1][j] + T[i][j + 1]

          return T[0][0]


_ Time Complexity:

  O(m * n) - Where m is the number of rows, and n is the number of columns, both solutions require
  polynomial time to calculate the number of unique paths.

_ Space Complexity:

  O(m * n) - The recursive solution's stack will reach this size. The iterative solution uses this
  amount of space to store the memoization table.