LeetCode开心刷题二十九天——62. Unique Paths*63. Unique Paths II**

迷南。 2023-08-17 15:14 128阅读 0赞

ADD：

DP Subject：100 DP formula

[https://blog.csdn.net/liuqiyao\_01/article/details/8765812][https_blog.csdn.net_liuqiyao_01_article_details_8765812]

63. Unique Paths II

Medium

938145FavoriteShare

A robot is located at the top-left corner of a *m* x *n* grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

![robot_maze.png][]

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

Note: *m* and *n* will be at most 100.

Example 1:

Input:
    [
      [0,0,0],
      [0,1,0],
      [0,0,0]
    ]
    Output: 2
    Explanation:
    There is one obstacle in the middle of the 3x3 grid above.
    There are two ways to reach the bottom-right corner:
    1. Right -> Right -> Down -> Down
    2. Down -> Down -> Right -> Right

BONUS:

1.for python for loop don't have actual meaning so even "\_" this kinds of thing can also used in for loop

for _ in range(5):
        print(_)

dp = [[0] * n for _ in range(m)]

using this method to initialize the two-dimension array

2.Python strip() 方法用于移除字符串头尾指定的字符（默认为空格）

import sys
    
    
    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            m,n=len(obstacleGrid),len(obstacleGrid[0])
            #attention:0*n first multiply n for m the rank easy confuse
            dp=[[0]*n for _ in range(m)]
            if obstacleGrid[0][0]==0:
                dp[0][0]=1
            for i in range(m):
                for j in range(n):
                    if obstacleGrid[i][j]==0:
                        if i==j==0:
                            continue
                        dp[i][j]=dp[i-1][j]+dp[i][j-1]
            return dp[m-1][n-1]
    
    solu=Solution()
    #obstacleGrid=input()
    
    
    myList2=[
      [0,0,0],
      [0,1,0],
      [0,0,0]
    ]
    print(solu.uniquePathsWithObstacles(myList2))

转载于:https://www.cnblogs.com/Marigolci/p/11308234.html

[https_blog.csdn.net_liuqiyao_01_article_details_8765812]: https://blog.csdn.net/liuqiyao_01/article/details/8765812
[robot_maze.png]: https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png