算法随想录第三十九天打卡|62.不同路径 , 63. 不同路径 II

发布时间:2024年01月19日

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]

总结

我应该从他的定义出发的,dp[i][j]的定义就是从开始坐标到当前坐标的路径的数量,所以我直接为0就表是有障碍了呀。

文章来源:https://blog.csdn.net/2303_79574965/article/details/135704769
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。