- 技术博客
- No.213 - LeetCode[63] Unique Paths II - 矩阵左上走右下的路径数 - 经典dp
class Solution {
public:
int uniquePathsWithObstacles(vector
<vector
<int>>& obstacleGrid
) {
int N
= obstacleGrid
.size();
if(N
<= 0) return 0;
int M
= obstacleGrid
[0].size();
if(M
<= 0) return 0;
vector
<vector
<int>> dp(N
+1,vector
<int>(M
+1,0));
if(obstacleGrid
[0][0] == 0) dp
[1][1] = 1;
for(int i
=1;i
<=N
;i
++){
for(int j
=1;j
<=M
;j
++){
if(obstacleGrid
[i
-1][j
-1] == 0)
dp
[i
][j
] += dp
[i
-1][j
] + dp
[i
][j
-1];
}
}
return dp
[N
][M
];
}
};
