力扣63
https://leetcode-cn.com/problems/unique-paths-ii/submissions/
dp题，不同路径加入了障碍物，但影响不了多少，只多了判断条件：
- 如果当前为障碍，dp[i][j]为0
- 如果左边为障碍，dp[i][j] = 上面
- 如果上面为障碍，dp[i][j] = 左边
- 否则才是dp[i][j] = 左边 + 上面
因为障碍的判断刚好是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
28
| public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
if (col == 0) return 0;
int[][] dp = new int[row][col];
boolean check = true;
for (int i = 0; i < row; i++) {
if(obstacleGrid[i][0] == 1) check = false;
dp[i][0] = check ? 1 : 0;
}
check = true;
for (int i = 0; i < col; i++) {
if(obstacleGrid[0][i] == 1) check = false;
dp[0][i] = check ? 1 : 0;
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[row - 1][col - 1];
}
|
解法倒是很简单，但是会有智障把障碍放在入口和出口？？？？？？？？？？？？？
值得注意的是在dp问题中，很多人会采取dp[m + 1][n + 1]的写法来帮助更好的符合生活形式（1开头而不是0开头），另外就是可以简化初始化过程，dp[0]和dp[n][0]作为初始化，则dp[1]也可符合递推关系式，无需额外初始化。
另外就是部分人会采用降一维来减少空间复杂度，只记录dp[n]
这些技巧性很强的东西我在这里不多说了，评论区一抓一大把，偶尔可以学学优化一下，但是这里我只希望记录最通用、最本质、最模板的方法，以便能在一个“复杂度允许的范围内最快速度做出题目”。
其他动态规划的题目可以点击这里
