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]

?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

視頻講解：動(dòng)態(tài)規(guī)劃，這次遇到障礙了| LeetCode：63. 不同路徑 II_嗶哩嗶哩_bilibili

思路

我本來想的是用高中的遇到障礙的題來解的，結(jié)果他沒說有幾個(gè)障礙，這個(gè)方法只能解決一個(gè)障礙的，就是減去經(jīng)過這個(gè)障礙的路徑。

我寫的錯(cuò)誤方法

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 #表示障礙的坐標(biāo)
                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:  # 遇到障礙物時(shí)，直接退出循環(huán)，后面默認(rèn)都是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]

總結(jié)

我應(yīng)該從他的定義出發(fā)的，dp[i][j]的定義就是從開始坐標(biāo)到當(dāng)前坐標(biāo)的路徑的數(shù)量，所以我直接為0就表是有障礙了呀。文章來源地址http://www.zghlxwxcb.cn/news/detail-808366.html