Day 41

01. 整数拆分（No. 343）

题目链接

代码随想录题解

<1> 题目

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

<2> 笔记

因为最终的结果是从 dp 数组中取出的，所以如果没有思路或者考虑递归的时候可以先从 dp 数组的 含义 作为切入点。

根据题目将 dp 数组的含义定为：dp[i] 为 正整数 i 拆分成 k 个数能获得的最大的乘积。

那这个 状态 能否转换呢？

一个整数的最大乘积可以转换为 两个加和等于这个整数的数的乘积 和 将这两个数做 拆分 之后再去求乘积，比如 5 可以转化为 4 + 1 也可以转化成拆分后的相加；第一个情况很好求出，从 1 遍历持续计算 (i - j) * j 即可：

那第二个如何求得呢？再回去看一下 dp 数组的含义正是 将一个数字拆分后得到的最大乘积，这其实就是第二种情况的最优解，因为此时可以保证拆分出来之后乘积达到最大。

于是可以采取这样的方法：遍历时从头开始遍历数组，来逐次比较以下的三个值：

dp[i] dp[i - j] * j (i - j) * j，取出其中的最大值作为 dp[i] 的值。

那么在取最大值的时候，为什么还要比较 dp[i] 呢？
因为在递推公式推导的过程中，每次计算 dp[i]，取最大的而已。

那为什么不比较 dp[i - j] * dp[j] 呢？
因为拆分要求的是两个以上，而 dp 数组的含义是 拆分后 的最大值，那如果是以上的情况其实就默认拆分成 四个及四个 以上了；所以 (i - j) * j 代表拆分成 两个 的情况，而 dp[i - j] * j 代表拆分成 两个以上的情况，这样其实就已经涵盖了所有的情况了。

dp 数组的初始化：直接初始化 dp[2] 即可，因为 dp[1] 和 dp[0] 在题目中是没有意义的。

遍历顺序：从前向后遍历。

<3> 代码

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 = 0; j < i; j++) {
                dp[i] = Math.max(dp[i], (i - j) * j);
                dp[i] = Math.max(dp[i], dp[i - j] * j);
            }
        }
        return dp[n];
    }
}

02. 不同的二叉搜索树（No. 96）

题目链接

代码随想录题解

<1> 题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

<2> 笔记

本题的 状态 还是比较好确认的，但是状态如何转移却极其困难；首先根据题目可以确定出 dp[i] 的含义大概率是由 i 个节点组成的不同的二叉搜索树有多少种。

先将 1 2 3 这三种情况的图画出

观察 n == 3 的时候的搜索树的图像，其是由三部分构成的：

• 头节点为 1
• 头节点为 2
• 头节点为 3

头节点为 1 的时候 仅存在右子树，观察一下，这个右子树的构成和 n == 2 的时候是相同的？

💡 这里说的相同的结构上的相同，指的是 1 的左子树是类似如下的这种情况

这正是 n == 2 的时候构成二叉树的结构，那是不是可以这样表示呢？

如果还是不太理解那再来看几个案例，假设 n == 6，此时看的是头节点为 4 的情况

左子树共有 4 - 1 也就是三个节点，这三个节点可以构成什么结构呢？

思考一下，和上面 n == 3 完全相同的结构，将这个结构作为左子树；右子树是由一大一小 两个数组成的搜索树结构，这个结构不也恰好是 n == 2 时的结构吗？此时的种数就是 dp[3] * dp[2]，最终就是这样的情况：

将头节点为 1 到 6 的情况全部遍历完就是 n == 6 的所有情况。

看到这里大家肯定也明白了，转移的状态 是 n == i 时的 结构，因为即使数字构成不一样，但只要是长度大小为 k 的递增序列就和 n == k 时候形成的结构是完全相同的，比如 112 113 114 形成的结构其实和 1 2 3 的结构是相同的。

这样只需要确认左子树和右子树各有 多少个数 即可

for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

<3> 代码

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