算法训练营day35 | {62.不同路径, 63.不同路径 II, 343.整数拆分, 96.不同的二叉搜索树}

第九章动态规划part02，找到子状态之间的规律、递推关系很关键。

62. 不同路径

1.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义：从坐标(0, 0)到达(i, j)一共有dp[i][j]种不同的走法。
  2. 确定递推公式: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  3. dp数组如何初始化: dp[0][?] 第一行都只有1种走法; dp[?][0] 第一列也只有1种走法
  4. 确定遍历顺序: 因为依赖左边和上面的dp值，所以从上到下，从左到右遍历
  5. 举例推导dp数组: 3行7列
    image.png
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 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];
    }
}

63. 不同路径 II

2.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i][j]的定义：从坐标(0, 0)到达(i, j)一共有dp[i][j]种不同的走法。
  2. 确定递推公式: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  3. dp数组如何初始化: dp[0][?] 第一行都只有1种走法; dp[?][0] 第一列也只有1种走法；如果遇到障碍物，则后面的都不到，设为0种走法
  4. 确定遍历顺序: 从上到下，从左到右遍历
  5. 举例推导dp数组: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    image.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
        int[][] dp = new int[m][n];
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) break;
            dp[0][j] = 1;
        }
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break;
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

343. 整数拆分

3.1 解题分析

  • 如何用DP？比如拆正整数10，会用到正整数为2、4、6、8时的最大乘积值，依赖于上一个状态。

    1
    2
    3
    (2) (8)->
       2 (6)->
          2  (4)...

  • dp[i]最大乘积是怎么得到的？其实可以从1遍历j，又两种渠道得到dp[i]:

    1. j * (i - j)
    2. j * dp[i - j]

  • 为什么j不用拆分？j是从1开始遍历的，拆分j的情况，再遍历j的过程中已经计算过了，因此可以推出递推公式。

  • 优化：拆分一个数n使之乘积最大，那么一定是拆分成m个近似相同的子树相乘才是最大的。例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。100的话 也是拆成m个近似数组的子数 相乘才是最大的。只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是最差也应该是拆成两个相同的可能是最大值。

    • 因此，j遍历只需要遍历到n/2就可以，后面没有必要继续遍历了，因为一定不是最大值。

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i]的定义：拆分数字i，可以得到的最大乘积为dp[i]
  2. 确定递推公式: dp[i] = max(j * (i - j), j * dp[i - j])
  3. dp数组如何初始化: dp[0] 和 dp[1]都没有意义，不应该初始化。 dp[2] = 1
  4. 确定遍历顺序: dp[i]是依赖于dp[i - j]的状态的，因此遍历i是从前往后遍历
  5. 举例推导dp数组: n = 10
    n=10 模拟dp数组值

3.2 解题小结

第一遍解题时dp[i]的递推公式写错了，我只计算了当前j下的拆法最优的结果，而不是dp[i] = max(之前所有 j 的最优结果, 当前 j 的最优结果)。导致覆盖了历史最优解。举个例子，n=10，我的代码的执行过程：

  • i = 10 当j = 3 时:
    1
    dp[10] = max(3 * 7, 3 * dp[7]) = max(21, 36) = 36
  • 已经算对了，但是继续循环，当j = 5时：
    1
    dp[10] = max(5 * 5, 5 * dp[5]) = max(25, 30) = 30
    36被覆盖成了30。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp [2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i/ 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

96. 不同的二叉搜索树

4.1 解题分析

假设dp[n]定义：1到n为节点组成的BST树的个数为dp[n]，来分析n=3的情况。dp[3]，就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量。

1
2
3
4
5
6
7
8
9
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

n=3模拟

动规五部曲：

  1. 确定dp数组以及下标的含义: dp[i]定义：1到i节点组成的二叉搜索树的个数为dp[i]
  2. 确定递推公式: dp[i] += dp[j - 1] * dp[i - j] 其中 j从1遍历到i，模拟不同的元素作为头节点的情况
  3. dp数组如何初始化: dp[0] = 1 空树也是一个BST树；dp[1] = 1
  4. 确定遍历顺序: 因为节点数为i的状态dp[i]是依赖i之前的节点数的状态，所以从小到大遍历
  5. 举例推导dp数组: 模拟n=3时，共有5个不同的BST，分别以1、2、3为头节点。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        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];
    }
}

4. 今日收获

  • 今天的后面两题，因为没有找到子状态之间的递推关系，都没什么思路。多思考规律在哪里，然后用动态规划五部曲来系统分析一次吧。
  • 学习时长：3.5小时
Leetcode > 动态规划
#Java #代码随想录
算法训练营day35 | {62.不同路径, 63.不同路径 II, 343.整数拆分, 96.不同的二叉搜索树}
http://paopaotangzu.xyz/cn/day35_leetcode/
作者
PROTON TANG
发布于
2026年1月20日
许可协议