062.Unique Paths I & II

Unique Paths 入门级动态规划,我一开始用递归做了一下,直接超时了//// 2333

二维数组动态规划

这里给机器人增加了障碍物,需要在递推式res[i][j]=res[i-1][j]+res[i][j-1]之前增加一个判断,

如果则res[i][j]=0,则res[i][j] = 0 (当然res初始化全部成0,所以可以直接跳过)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int i, j, m = obstacleGrid.size(), n = obstacleGrid[0].size();
// 默认所有地方都是堵着的
vector<vector<int> > dp(m, vector<int>(n, 0));
// 两头堵住了
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
//初始化动态规划矩阵dp
for (i = 0; i < m&&obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
for (i = 1; i < m; i++) {
for (j = 1; j < n; j++) {
if(obstacleGrid[i][j]==0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];

}
};

一维数组

  • 如果有阻碍,那么当前位置肯定是到达不了的,所以 dp[j] = 0
  • 如果没有阻碍,那么到当前位置分为两个部分:上一行第j个 + 本行第j-1个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
vector<int> dp(obstacleGrid[0].size(), 0);

for (int i = 0; i < obstacleGrid[0].size() && obstacleGrid[0][i] == 0; ++i)
{
dp[i] = 1;
}

for (int i = 1; i < obstacleGrid.size(); ++i)
{
if (obstacleGrid[i][0] == 1)
{
dp[0] = 0;
}

for (int j = 1; j < obstacleGrid[i].size(); ++j)
{
dp[j] = obstacleGrid[i][j] == 0 ? dp[j] + dp[j - 1] : 0;
}
}

return dp.back();
}
};

递归算法

本方法会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// 目前在第i行,第j列
int uniquePaths(vector<vector<int>>& obstacleGrid, int i, int j) {
if (i == obstacleGrid.size() - 1 && j == obstacleGrid[0].size() - 1 && obstacleGrid[i][j] == 0)
return 1;
if (i + 1 < obstacleGrid.size() && j + 1 < obstacleGrid[0].size() && obstacleGrid[i + 1][j] == 0 && obstacleGrid[i][j + 1] == 0)
return uniquePaths(obstacleGrid, i + 1, j) + uniquePaths(obstacleGrid, i, j + 1);
if (i + 1 < obstacleGrid.size() && obstacleGrid[i + 1][j] == 0)
return uniquePaths(obstacleGrid, i + 1, j);
if (j + 1 < obstacleGrid[0].size() && obstacleGrid[i][j + 1] == 0)
return uniquePaths(obstacleGrid, i, j + 1);
return 0;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] == 1)
return 0;
return uniquePaths(obstacleGrid, 0, 0);
}
};

小结

看起来递归是最挫的方法,但是最好理解。

二维数组的方法其实也挺好理解的,一维数组感觉有点费解,不太显然的感觉。

作者

mmmwhy

发布于

2018-09-02

更新于

2021-12-08

许可协议

评论