62. Unique Paths

問題の説明

1-bfsに近い

コード1

    def uniquePaths(self, m: int, n: int) -> int:
        start = [0, 0]; end = [m - 1, n - 1]
        ans = 0
        dq = collections.deque([start])
        directions = [[0, 1], [1, 0]]
        while dq:
            i, j = dq.popleft()
            if [i, j] == end:
                ans += 1
                continue
            for d in directions:
                x, y = i + d[0], j + d[1]
                if x < m and y < n:
                    dq.append([x, y])
                    
        return ans

アクセス2-ケース数

コード2

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

64. Minimum Path Sum

問題の説明

に近づく

コード1

    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid); n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if i >= 1 and j >= 1: grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
                elif i >= 1: grid[i][j] += grid[i - 1][j]
                elif j >= 1: grid[i][j] += grid[i][j - 1]
        return grid[-1][-1]