62.不同路径-动态规划

一、62. 不同路径 1.1、题目描述

1.2.1、排列组合

1.2.2、动态规划

我们令 dp[i][j] 是到达 i, j 最多路径

动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1],

注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        dp = [[1] * n] + [[1] + [0] * (n-1) for _ 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[-1][-1]

1.2.3、优化：每次只记录上一行的数据， 当前行的位置由左边和上边的和

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        pre = [1] * n   # 上一行
        cur = [1] * n   # 当前行
        
        for i in range(1, m):
            for j in range(1, n):
                cur[j] = pre[j] + cur[j-1]
            pre = cur
            
        return pre[-1]

1.2.4、优化（这个是看别人的，但是没怎么看懂）

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        cur = [1] * n   # 当前行
        
        for i in range(1, m):
            for j in range(1, n):
                cur[j] += cur[j-1]
            print(cur)
            
        return cur[-1]

二、63. 不同路径 II 2.1、题目描述

2.2.1、参照1.2.3

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return  0
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        pre = [1] * n
        cur = [1] * n
        
        for i in range(m):
            for j in range(n):
                # print(i, j, obstacleGrid[i][j], pre, cur)
                if i == 0:
                    if obstacleGrid[i][j] == 1 or (j > 0 and cur[j-1] == 0):
                        cur[j] = 0
                    else:
                        cur[j] = 1
                else:
                    if j == 0:
                        if obstacleGrid[i][j] == 1 or (i > 0 and pre[j] == 0):
                            cur[j] = 0
                        else:
                            cur[j] = 1
                    else:
                        if obstacleGrid[i][j] == 1:
                            cur[j] = 0
                        else:
                            cur[j] = pre[j] + cur[j-1]
            pre = cur
        return pre[-1]