文章目录
- Day 41
- 01. 整数拆分(No. 343)
- 题目
- 笔记
- 代码
- 02. 不同的二叉搜索树(No. 96)
- 题目
- 笔记
- 代码
Day 41
01. 整数拆分(No. 343)
题目链接
代码随想录题解
题目
给定一个正整数 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
笔记
因为最终的结果是从 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]
在题目中是没有意义的。
遍历顺序:从前向后遍历。
代码
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)
题目链接
代码随想录题解
题目
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
示例 2:
输入:n = 1
输出:1
提示:
1 <= n <= 19
笔记
本题的 状态 还是比较好确认的,但是状态如何转移却极其困难;首先根据题目可以确定出 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];}}
代码
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];}}