Related: Unique Paths 2
Intuition
- Use DFS to get each path that goes from start to finish.
- In so doing, do not recompute what you already computed.
- Alternatively without memoization, you can solve this problem by initializing the last row and last column with 1’s, then using the formula and in the correct order starting from the bottom right -1, -1
- This code can be made even better by using just 1 array. The trick here is that once you compute one row, you can use that row as the previous and the current row since going to the right and down means the same thing as going to the previous combination + the current one.
- This is a very important point, and is the key to understanding most tabulation based problems when solving them in an efficient way.
Runtime
- For memoization and tabulation, it is time and space
- For low space dp, the space goes down to to hold the one row needed.
Code
1D DP
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [0] * n
dp[-1] = 1
for _ in reversed(range(m)):
for c in reversed(range(n - 1)):
dp[c] = dp[c] + dp[c + 1]
return dp[0]Tabulation DP
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
nums = []
for i in range(m - 1):
nums.append([0] * (n - 1) + [1])
nums.append([1] * n)
for i in range(m - 2, -1, -1):
for j in range(n - 2, -1, -1):
nums[i][j] += nums[i + 1][j] + nums[i][j + 1]
return nums[0][0]DFS Memoization
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
def is_out_of_bounds(x, y):
return not (0 <= x < m and 0 <= y < n)
@lru_cache
def r(x, y):
if (x, y) == (m - 1, n - 1):
return 1
res = 0
for (i, j) in [(x + 1, y), (x, y + 1)]:
if not is_out_of_bounds(i, j):
res += r(i, j)
return res
return r(0, 0)Notes
References
https://leetcode.com/problems/unique-paths/?envType=daily-question&envId=2023-09-03