动态规划-不同路径

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]

优化

当前值只与左边和上边的值有关。

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]