LeetCode 62 不同路径
🟢 简单
无障碍物
https://leetcode.cn/problems/unique-paths/
显然递归
class Solution {
public:
int uniquePaths(int m, int n) {
if(m==1&&n==1) return 1;
if(n<0||m<0) return 0;
return uniquePaths(m,n-1)+uniquePaths(m-1,n);
}
};
改进为dp
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m+1][n+1];
memset(dp,0,sizeof dp);
dp[0][1] = 1;
for(int i = 1;i<=m;i++){
for(int j = 1;j<=n;j++){
dp[i][j] = dp[i][j-1]+dp[i-1][j];
}
}
return dp[m][n];
}
};
发现for循环中只用到了上面一行和左边一个，因此
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[n+1];
memset(dp,0,sizeof dp);
int left = 1;
for(int i = 1;i<=m;i++){
for(int j = 1;j<=n;j++){
dp[j] = left+dp[j];
left = dp[j];
}
left = 0;
}
return dp[n];
}
};
有障碍物
https://leetcode.cn/problems/unique-paths-ii/
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
int dp[row+1][col+1];
memset(dp,0,sizeof dp);
dp[0][1] =1;
for(int i = 1;i<=row;i++){
for(int j = 1;j<=col;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
if(obstacleGrid[i-1][j-1]==1) dp[i][j]=0;
}
}
return dp[row][col];
}
};