算法随想录第三十九天打卡|62.不同路径， 63. 不同路径 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法随想录第三十九天打卡|62.不同路径， 63. 不同路径 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

62.不同路径

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

代码随想录

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

class Solution(object):
    def uniquePaths(self, m, n):
        if m==1 and n==1:
            return 1
        dp=[[0]*n]*m
        dp[0][0]=1
        for x in range(m):
            for y in range(n):
                if x>0 and y>0:
                    dp[x][y]=dp[x-1][y]+dp[x][y-1]
                if x==0 or y==0:
                    dp[x][y]=1
        return dp[m-1][n-1]

总结

把m和n弄反了。

63. 不同路径 II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html

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

思路

我本来想的是用高中的遇到障碍的题来解的，结果他没说有几个障碍，这个方法只能解决一个障碍的，就是减去经过这个障碍的路径。

我写的错误方法

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m=0
        n=0
        x=len(obstacleGrid)
        y=len(obstacleGrid[0])
        if x==1 and y==1:
            if obstacleGrid[0][0]==1:
                return 0
            return 1
        for i in range(x):
            for j in range(y):
                if obstacleGrid[i][j]==1:  #表示遇到障碍
                    if i==x-1 and j==y-1:
                        return 0 
                    m=i
                    n=j #表示障碍的坐标
                if i>0 and j>0:
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
                elif (i==0 or j==0) and (i>0 or j>0):
                    obstacleGrid[i][j]=1
        pre=obstacleGrid[m][n]*obstacleGrid[x-m-1][y-n-1]
        return obstacleGrid[x-1][y-1]-pre

答案

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
            return 0
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 0:  # 遇到障碍物时，直接退出循环，后面默认都是0
                dp[i][0] = 1
            else:
                break
        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]