当前位置：首页 > news >正文

代码随想录算法训练营第三十三天

news 2025/7/29 15:21:36

LeetCode.62 不同路径

题目链接不同路径

题解

class Solution {public int uniquePaths(int m, int n) {// dp表示到达ij有多少条路径int[][] dp = new int[110][110];dp[1][1] = 1;for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int j = 0;j<n;j++){dp[0][j] = 1;}for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

解题思路

这段代码是用来解决不同路径问题的动态规划实现。下面我将详细解析这段代码的思路、实现细节以及可能的优化点。

一、问题背景：不同路径问题

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。问总共有多少条不同的路径？

例如，当 m=3，n=7 时，总共有 28 条不同路径。

二、代码思路解析

1. 动态规划定义

dp[i][j] 表示：从左上角 (0,0) 出发，到达网格 (i,j) 时的不同路径总数。

2. 边界条件

当 i=0（第一行）时，机器人只能一直向右移动，所以到达 (0,j) 的路径只有 1 条，即 dp[0][j] = 1。
当 j=0（第一列）时，机器人只能一直向下移动，所以到达 (i,0) 的路径只有 1 条，即 dp[i][0] = 1。
代码中初始化了 dp[1][1] = 1，但实际通过后续对第一行和第一列的初始化，这个值会被覆盖（若 m 和 n 大于 1），可以忽略。

3. 状态转移方程

对于网格中任意一点 (i,j)（非第一行、非第一列），机器人只能从上方 (i-1,j) 或左方 (i,j-1) 移动而来。
因此，到达 (i,j) 的路径数 = 到达 (i-1,j) 的路径数 + 到达 (i,j-1) 的路径数，即：
dp[i][j] = dp[i-1][j] + dp[i][j-1]

4. 遍历顺序

从 i=1 到 i=m-1（行遍历），从 j=1 到 j=n-1（列遍历），依次计算每个网格的路径数，最终 dp[m-1][n-1] 即为答案。

三、代码细节说明

数组初始化：
int[][] dp = new int[110][110];
这里创建了一个 110x110 的二维数组，足够覆盖题目中常见的 m 和 n 范围（通常题目约束 m,n <= 100）。

for(int i = 0;i<m;i++){dp[i][0] = 1;  // 第一列全为1
}
for(int j = 0;j<n;j++){dp[0][j] = 1;  // 第一行全为1
}

这两个循环正确初始化了边界条件，确保第一行和第一列的路径数均为 1。

状态转移计算：
```
for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}
}
```
双层循环遍历网格的非边界部分，通过上方和左方的路径数累加得到当前网格的路径数。
返回结果：
return dp[m-1][n-1];
由于数组下标从 0 开始，右下角的坐标为 (m-1, n-1)，直接返回该位置的路径数即可。

四、测试案例验证

以 m=3，n=7 为例：

初始化第一行 dp[0][0..6] = [1,1,1,1,1,1,1]，第一列 dp[0..2][0] = [1,1,1]。
计算 dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2。
计算 dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3。
... 依次类推，最终 dp[2][6] = 28，与预期结果一致。

LeetCode.63. 不同路径 II

题目链接不同路径 II

题解

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[110][110];for(int i = 0;i<m;i++){if(obstacleGrid[i][0] == 1) {break;}dp[i][0] = 1;}for(int j = 0;j<n;j++){if(obstacleGrid[0][j] == 1) {break;}dp[0][j] = 1;}for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];if(obstacleGrid[i][j] == 1) dp[i][j] = 0;}}return dp[m-1][n-1];}
}

解题思路

这段代码是用来解决带障碍物的不同路径问题的动态规划实现。相比基础的不同路径问题，这个问题增加了障碍物的限制，我们来详细分析这段代码的思路和实现细节。

一、问题背景：带障碍物的不同路径

一个机器人位于一个 m x n 网格的左上角（起始点）。机器人每次只能向下或者向右移动一步。网格中可能存在障碍物，机器人不能通过障碍物。求从左上角到右下角总共有多少条不同的路径？

例如，对于下面的网格（1 表示障碍物）：

[[0,0,0],[0,1,0],[0,0,0]
]

答案是 2，因为有两条不同的路径可以避开障碍物到达终点。

二、代码思路解析

1. 动态规划定义

dp[i][j] 表示：从左上角 (0,0) 出发，到达网格 (i,j) 时的不同路径总数（若 (i,j) 是障碍物，则路径数为 0）。

2. 边界条件处理

对于第一列（j=0）：
- 从 i=0 开始遍历，如果遇到障碍物（obstacleGrid[i][0] == 1），则后续所有单元格都无法到达（直接 break）。
- 否则，dp[i][0] = 1（只能从上方一直向下移动到达）。
对于第一行（i=0）：
- 从 j=0 开始遍历，如果遇到障碍物（obstacleGrid[0][j] == 1），则后续所有单元格都无法到达（直接 break）。
- 否则，dp[0][j] = 1（只能从左方一直向右移动到达）。

3. 状态转移方程

对于非边界的单元格 (i,j)：
- 先计算正常情况下的路径数：dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方或左方到达）。
- 如果当前单元格是障碍物（obstacleGrid[i][j] == 1），则路径数为 0，即 dp[i][j] = 0。

4. 最终结果

返回 dp[m-1][n-1]，即到达右下角的路径总数。

三、代码细节说明

初始化网格大小：
```
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
```
通过输入的障碍物网格获取行数 m 和列数 n。
DP 数组初始化：
```
int[][] dp = new int[110][110];
```
创建一个 110x110 的二维数组，足够覆盖常见的网格大小约束。
第一列边界处理：
```
for(int i = 0;i<m;i++){if(obstacleGrid[i][0] == 1) {break;  // 遇到障碍物，后续单元格都无法到达}dp[i][0] = 1;
}
```
从顶部开始向下遍历第一列，一旦遇到障碍物，就终止循环，确保障碍物下方的单元格路径数保持默认的 0。

第一行边界处理：

for(int j = 0;j<n;j++){if(obstacleGrid[0][j] == 1) {break;  // 遇到障碍物，后续单元格都无法到达}dp[0][j] = 1;
}

从左侧开始向右遍历第一行，逻辑与第一列处理类似。

非边界单元格计算：

for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];  // 先计算正常路径数if(obstacleGrid[i][j] == 1) dp[i][j] = 0;  // 若有障碍物则路径数为0}
}

双层循环遍历网格的非边界部分，先按正常逻辑累加路径数，再判断当前位置是否为障碍物并修正路径数。

四、测试案例验证

以示例网格为例：

[[0,0,0],[0,1,0],[0,0,0]
]

初始化第一列：dp[0][0]=1，dp[1][0]=1，dp[2][0]=1（无障碍物）。
初始化第一行：dp[0][0]=1，dp[0][1]=1，dp[0][2]=1（无障碍物）。
计算 dp[1][1]：先算 dp[0][1] + dp[1][0] = 2，但因 (1,1) 是障碍物，最终 dp[1][1] = 0。
计算 dp[1][2]：dp[0][2] + dp[1][1] = 1 + 0 = 1（无障碍物，结果为 1）。
计算 dp[2][1]：dp[1][1] + dp[2][0] = 0 + 1 = 1（无障碍物，结果为 1）。
计算 dp[2][2]：dp[1][2] + dp[2][1] = 1 + 1 = 2（最终答案为 2）。

结果与预期一致，验证了代码的正确性。

LeetCode.96 不同的二叉搜索树

题目链接不同的二叉搜索树

题解

class Solution {public int numTrees(int n) {int[] dp = new int[25];dp[0] = 1;for(int i = 1;i<=n;i++){for(int j = 1;j<=i;j++){dp[i] += dp[j-1] * dp[i-j]; }}return dp[n];}
}

解题思路

这段代码实现了计算不同结构的二叉搜索树数量的功能，使用的是动态规划的思想。

代码解析：

定义了一个numTrees方法，接收一个整数n作为参数，返回值是int类型，表示 n 个节点能组成的不同二叉搜索树的数量。
创建了一个长度为 25 的数组dp，用于存储中间计算结果。dp[i]表示 i 个节点能组成的不同二叉搜索树的数量。
初始化dp[0] = 1，这是一个边界条件，表示 0 个节点时只有 1 种情况（空树）。
使用两层循环计算dp数组：
- 外层循环i从 1 到 n，表示计算 i 个节点的情况
- 内层循环j从 1 到 i，表示以 j 为根节点的情况
- 当以 j 为根节点时，左子树有 j-1 个节点，右子树有 i-j 个节点
- 因此dp[i]等于所有可能的左子树数量乘以右子树数量的和
最后返回dp[n]，即 n 个节点能组成的不同二叉搜索树的数量

这个问题其实是一个经典的卡特兰数（Catalan number）问题，代码通过动态规划的方式计算出了第 n 个卡特兰数，也就是 n 个节点所能组成的不同二叉搜索树的数量。

总结

以上三个问题均用动态规划求解。62 题算 m×n 网格不同路径数，dp [i][j] 为到 (i,j) 的路径数，边界为首行首列全 1，转移方程为 dp [i][j] = 左 + 上。63 题加障碍物，遇障后首行 / 列后续为 0，当前有障则 dp 为 0。96 题算 n 个节点二叉搜索树数，是卡特兰数问题，dp [i] 为 i 个节点的树数，转移方程为左子树数 × 右子树数之和。

查看全文

http://www.lryc.cn/news/603011.html