DP path sum

Path sum is supposed to be solved bug-free.

62. Unique Paths

Bottom-up

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1:return 1
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                dp[i][j] += (dp[i-1][j] if i-1>=0 else 0) + (dp[i][j-1] if j-1>=0 else 0)
        return dp[-1][-1]

Top-down

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==1:return 1
        from functools import lru_cache
        @lru_cache(None)
        def dp(i,j):
            if i<0 or j<0:return 0
            if i==j and j==0:return 1
            return dp(i-1, j)+dp(i, j-1)
        return dp(m-1, n-1)

63. Unique Paths II

Bottom-up

Time complexity is O(n²)

Space complexity is O(n²)

class Solution:
    def uniquePathsWithObstacles(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        if A[0][0]==1 or A[-1][-1]==1:return 0
        dp = [[0]*C for _ in range(R)]
        dp[0][0] = 1
        for i in range(R):
            for j in range(C):
                if not A[i][j]:
                    dp[i][j] += (dp[i-1][j] if i-1>=0 else 0) + (dp[i][j-1] if j-1>=0 else 0)
        return dp[-1][-1]

Top-down

We must use memo to speed up. If not, the time complexity will be exponential and we will get TLE.

from functools import lru_cache
class Solution:
    def uniquePathsWithObstacles(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        if A[0][0]==1 or A[-1][-1]==1:return 0
        @lru_cache(None)
        def dp(i,j):
            if i<0 or j<0:return 0
            if A[i][j]:return 0
            if i==0 and j==0:return 1
            return dp(i-1,j)+dp(i,j-1)
        return dp(R-1, C-1)