[LeetCode] Unique Paths 1&2
1362 ワード
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i > 0) dp[i][j] += dp[i-1][j];
if (j > 0) dp[i][j] += dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
if (i > 0) dp[i][j] += dp[i-1][j];
if (j > 0) dp[i][j] += dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};