LeetCode 63. 不同路径 II C#
原题链接
中等
作者:
hpstory
,
2022-06-23 17:37:50
,
所有人可见
,
阅读 121
C# 二维代码
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.Length, m = obstacleGrid[0].Length;
// 到点n,m不同路径数量
int[,] dp = new int[n, m];
// 遇到障碍物跳过列剩余元素
for (int i = 0; i < n; i++){
if (obstacleGrid[i][0] == 1) break;
dp[i, 0] = 1;
}
// 遇到障碍物跳过行剩余元素
for (int j = 0; j < m; j++){
if (obstacleGrid[0][j] == 1) break;
dp[0, j] = 1;
}
for (int i = 1; i < n; i++){
for (int j = 1; j < m; j++){
if(obstacleGrid[i][j] != 1){
dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
}
}
}
return dp[n - 1, m - 1];
}
}
C# 一维代码
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.Length, m = obstacleGrid[0].Length;
int[] dp = new int[m];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (obstacleGrid[i][j] == 1){
dp[j] = 0;
continue;
}
if(j > 0 && obstacleGrid[i][j] == 0){
dp[j] = dp[j] + dp[j - 1];
}
}
}
return dp[m - 1];
}
}