每天一道算法题【蓝桥杯】【不同路径Ⅱ】

思路

这道题和上一题的最大不同在于多了个障碍物
所以只需要让障碍物处dp表的值为0即可

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
using namespace std;
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& ob) {int m = ob.size(), n = ob[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));  //创建dp表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];  //没有障碍物才等于上一格子加左一格子，否则为0//填入dp表return dp[m][n];}
};