文章目录

    • 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 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

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