62.不同路徑

image.png

第一種解法 基本DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for i in range(m)] # 初始化第一行第一列全為1 
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

優(yōu)化

當(dāng)前值只與左邊和上邊的值有關(guān)。

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

63. 不同路徑 Ⅱ

image.png

image.png

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid) # 行
        n = len(obstacleGrid[0]) # 列
        if n == 0 or m == 0: return 0
        dp = [[1] * n for _ in range(m)]
        # 第一行中若存在1，則第一個1及其后面的均初始化為0
        if 1 in obstacleGrid[0]:
            ind = obstacleGrid[0].index(1)
            for i in range(ind, n):
                dp[0][i] = 0
        
        # 第一列中若存在1，則第一個1及其后面的均初始化為0
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                for k in range(i, m):
                    dp[k][0] = 0
                break
    
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]