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

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] 即为答案。

三、代码细节说明

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

2. 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。

3. 状态转移计算：

   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];
       }
   }
   

    

   双层循环遍历网格的非边界部分，通过上方和左方的路径数累加得到当前网格的路径数。

4. 返回结果：
   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]，即到达右下角的路径总数。

三、代码细节说明

1. 初始化网格大小：

   int m = obstacleGrid.length;
   int n = obstacleGrid[0].length;
   

    

   通过输入的障碍物网格获取行数 m 和列数 n。

2. DP 数组初始化：

   int[][] dp = new int[110][110];
   

    

   创建一个 110x110 的二维数组，足够覆盖常见的网格大小约束。

3. 第一列边界处理：

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

    

   从顶部开始向下遍历第一列，一旦遇到障碍物，就终止循环，确保障碍物下方的单元格路径数保持默认的 0。

4. 第一行边界处理：

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

    

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

5. 非边界单元格计算：

   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];
    }
}

解题思路

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

代码解析：

1. 定义了一个numTrees方法，接收一个整数n作为参数，返回值是int类型，表示 n 个节点能组成的不同二叉搜索树的数量。

2. 创建了一个长度为 25 的数组dp，用于存储中间计算结果。dp[i]表示 i 个节点能组成的不同二叉搜索树的数量。

3. 初始化dp[0] = 1，这是一个边界条件，表示 0 个节点时只有 1 种情况（空树）。

4. 使用两层循环计算dp数组：

   • 外层循环i从 1 到 n，表示计算 i 个节点的情况
   • 内层循环j从 1 到 i，表示以 j 为根节点的情况
   • 当以 j 为根节点时，左子树有 j-1 个节点，右子树有 i-j 个节点
   • 因此dp[i]等于所有可能的左子树数量乘以右子树数量的和

5. 最后返回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 个节点的树数，转移方程为左子树数 × 右子树数之和。