不同路径的条数,不同路径 leetcode

题目描述

一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1

输入obstacleGrid  [[0,0,0],[0,1,0],[0,0,0]]输出2解释3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右

示例 2

输入obstacleGrid  [[0,1],[0,0]]输出1

提示

m  obstacleGrid.lengthn  obstacleGrid[i].length1 < m, n < 100obstacleGrid[i][j] 为 0 或 1

通过次数

419.8K

提交次数

1M

通过率

41.2%

思路和题解

动态规划和第62题62不同路径类似的思路只不过加一个判断条件如果当前位置有障碍物那么到达该位置的路径为0。

代码

class Solution {public:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {        int dp[101][101];        int ans;        int mobstacleGrid.size();        int nobstacleGrid[0].size();        if(obstacleGrid[0][0]1) return 0;        dp[1][1]1;        for(int i1;i<m;i) dp[i][0]0;        for(int i2;i<n;i)        {            if(obstacleGrid[0][i-1]1) dp[1][i]0;            else dp[1][i]dp[1][i-1];        }        for(int i2;i<m;i)        {            for(int j1;j<n;j)            {                if(obstacleGrid[i-1][j-1]1)                {                    dp[i][j]0;                }                else                {                    dp[i][j]dp[i-1][j]dp[i][j-1];                }            }        }        return dp[m][n];    }};