随想录日记part32
t i m e ： time： time： 2024.03.30
主要内容：今天开始要学习动态规划的相关知识了，今天的内容主要涉及两个方面：
不同路径 ； 不同路径 II。
- 62.不同路径
- 63. 不同路径 II
动态规划五部曲：
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组
Topic1不同路径
题目：
一个机器人位于一个 m ∗ n m *n m∗n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：
m
=
3
,
n
=
7
m = 3, n = 7
m=3,n=7
输出：
28
28
28
思路：
按照上面的五个步骤给出下面的代码：
代码如下：
class Solution {
public int uniquePaths(int m, int n) {
// 【1】dp[m][n]表示到(m,n)总走法
int[][] dp = new int[m + 1][n + 1];
// 【3】初始化
for (int i = 1; i <= n; i++) {
dp[1][i] = 1;
}
for (int i = 1; i <= m; i++) {
dp[i][1] = 1;
}
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
// 【2】.确定递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}
时间复杂度：
O
(
m
×
n
)
O(m × n)
O(m×n)
空间复杂度：
O
(
m
×
n
)
O(m × n)
O(m×n)
Topic2不同路径||
题目：
一个机器人位于一个 m x n m x n mxn 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
输入：
o
b
s
t
a
c
l
e
G
r
i
d
=
[
[
0
,
0
,
0
]
,
[
0
,
1
,
0
]
,
[
0
,
0
,
0
]
]
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
obstacleGrid=[[0,0,0],[0,1,0],[0,0,0]]
输出：
2
2
2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
【1】 向右 -> 向右 -> 向下 -> 向下
【2】 向下 -> 向下 -> 向右 -> 向右
思路：
按照上面的五个步骤给出下面的代码，在注释中给出具体的思路：
整体代码如下：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 【1】dp[m][n]表示到(m,n)总走法
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
// 【3】.dp数组如何初始化
int flag = 0;
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1 && flag == 0) {
dp[i][0] = -1;
flag = 1;
} else if (obstacleGrid[i][0] == 0 && flag == 0)
dp[i][0] = 1;
else if (obstacleGrid[i][0] == 0 && flag == 1)
dp[i][0] = 0;
else
dp[i][0] = -1;
}
flag = 0;
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1 && flag == 0) {
dp[0][i] = -1;
flag = 1;
} else if (obstacleGrid[0][i] == 0 && flag == 0)
dp[0][i] = 1;
else if (obstacleGrid[0][i] == 0 && flag == 1)
dp[0][i] = 0;
else
dp[0][i] = -1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1)
dp[i][j] = -1;
else {
if (dp[i - 1][j] < 0 && dp[i][j - 1] < 0)
dp[i][j] = 0;
else if (dp[i - 1][j] < 0)
dp[i][j] = dp[i][j - 1];
else if (dp[i][j - 1] < 0)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
if (dp[m - 1][n - 1] < 0)
return 0;
return dp[m - 1][n - 1];
}
}
时间复杂度：
O
(
m
×
n
)
O(m × n)
O(m×n)
空间复杂度：
O
(
m
×
n
)
O(m × n)
O(m×n)
