题目来源
本题来源为：
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
题目解析
本题是在不同路径I的基础上加了一个障碍物。
机器人在行走过程中要越过障碍物。
算法原理
1.状态表示
经验+题目要求
对于本题而言就是：
dp[i][j]表示：到达[i,j]位置的时候，一共有多少种方法
2.状态转移方程
其实本题的状态转移方程是很好推的，只用在原来那道不同路径I的基础上加一层判断即可，判断有无障碍物，有障碍物就为0
因此状态方程为：
3.初始化
本题初始化跟之前不同路径I的初始化是一样的。详细讲解过程在不同路径I中详细介绍过
4.填表顺序
从上往下填每一行，每一行从左往右
5.返回值
返回dp[m][n]
代码实现
动态规划的代码基本就是固定的四步：
1.创建dp表 2.初始化 3.填表 4.返回值
本题完整代码实现：
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& ob) { // int m=ob.size(),n=ob[0].size(); //创建dp表 vector<vector<int>> dp(m+1,vector<int>(n+1)); //初始化 dp[1][0]=1; //填表 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { //判断是否为障碍物 if(ob[i-1][j-1]==0) { //抄状态转移方程 dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } return dp[m][n]; } };
时间复杂度：O(MN)
空间复杂度：O(MN)
