动态规划--unique paths 2

刺骨的言语ヽ痛彻心扉 2022-05-23 09:09 136阅读 0赞

1、题目：

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

2、解答：这个比上个问题，多了一些不可达的点。也就是边界条件多了一些。

3、代码

C++代码

class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
           int m = obstacleGrid.size();
           int n = obstacleGrid[0].size();
           vector<vector<int> > dp(m+1,vector<int>(n+1,0));
           //dp[0][1] = 1 设置为1 是为了统一边界。即走第一个格子的时候，为1，这个设置，自己好好琢磨
           //dp[0][1] = 1 设置这两个中的一个为1
            dp[1][0] = 1;
            
           for(int i=1;i<=m;i++)
               for(int j=1;j<=n;j++)
                   if(!obstacleGrid[i-1][j-1])
                       dp[i][j] = dp[i-1][j] + dp[i][j-1];
           return dp[m][n];
        }
    };

python代码

class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            m,n = len(obstacleGrid),len(obstacleGrid[0])
            path = [[0 for i in range(n+1)] for j in range(m+1)]
            
            path[0][1] = 1
            
            for i in range(1,m+1):
                for j in range(1,n+1):
                    if  obstacleGrid[i-1][j-1] != 1:
                        path[i][j] = path[i-1][j] + path[i][j-1]
                        
            return path[-1][-1]

[robot_maze.png]: https://leetcode.com/static/images/problemset/robot_maze.png