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 个节点的树数，转移方程为左子树数 × 右子树数之和。
)
