代码随想录算法训练营第三十八天| 动态规划02

62. 不同路径

本题大家掌握动态规划的方法就可以。 数论方法 有点非主流，很难想到。

代码随想录

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili

注意点：

1. dp表示的是从原点到坐标点的路径有几条

2. 递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1]

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

63. 不同路径II

代码随想录

视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili

在上一题的基础上做改动：

1. 如果出发点和目标点有障碍物则返回0

2. 初始化时，如果当前格有障碍物，则后续行/列的dp值均为0

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