AcWing LeetCode63. LeetCode63
原题链接
简单
作者:
Sheldon__
,
2022-08-17 00:19:01
,
所有人可见
,
阅读 137
[LeetCode63]
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& g) {
int n = g.size(), m = g[0].size();
vector<vector<long long>> f(n, vector<long long>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(g[i][j]) continue;//如果是障碍物就不能走
if(!i && !j) f[i][j] = 1;//如果在左上角的话,就只有一种方案,就是本身
if(i > 0) f[i][j] += f[i - 1][j];
if(j > 0) f[i][j] += f[i][j - 1];
}
return f[n - 1][m - 1];
}
};
/*
状态表示
集合:所有从起点走到(i,j)的路径
属性:数量
状态计算
f[i][j]可以根据上一步是从上边下来的还是从左边过来的分成两种
f[i][j] = f[i - 1][j] + f[i][j - 1]
*/