Leetcode # 62. Unique Paths

https://leetcode.com/problems/unique-paths/

Solution

Time Complexity: O(m * n)
Space Complexity: O(m * n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def __init__(self):
    self.paths = {}
    self.paths[(0, 0)] = 1

  def uniquePaths(self, m: int, n: int) -> int:
    coord = (m - 1, n - 1)
    y, x = coord
    if x < 0 or y < 0: return 0
    if coord in self.paths: return self.paths[coord]
    
    self.paths[coord] = self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

    return self.paths[coord]
    

Last Updated on 2023/08/16 by A1go