代码随想录算法训练营DAY39｜62.不同路径、63. 不同路径 II

忙。。后两题先跳过

62.不同路径

• 题目链接：62.不同路径

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp=[[0 for a in range(n)] for b in range(m)]
        print(dp)
        dp[0][0]=1

        for i in range(m):
            for j in range(n):
                if j-1>=0 and i-1>=0:
                    dp[i][j]=dp[i][j-1]+dp[i-1][j]
                elif j-1<0 and i-1>=0:
                    dp[i][j]=dp[i-1][j]
                elif i-1<0 and j-1>=0:
                    print(i,j)
                    dp[i][j]=dp[i][j-1]
                else:
                    continue
        
        return dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

63. 不同路径 II

• 题目链接：63. 不同路径 II
• 某处有障碍，则到达某处的方法为0

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])

        if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
            return 0

        dp = [[0 for i in range(n)]for j in range(m)]
        dp[0][0]=1

        for i in range(m):
            if obstacleGrid[i][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 k in range(1, m):
            for l in range(1, n):
                if obstacleGrid[k][l]:
                    continue
                else:
                    dp[k][l]=dp[k-1][l] + dp[k][l-1]
        
        return dp[m-1][n-1] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34