DAY40休息日,本篇为DAY41的内容
文章目录
- 343.整数拆分
- 思路
- dp含义
- 递推公式(难点)
- 初始化
- 遍历顺序
- 打印
- CPP代码
- 数学方法
- 归纳证明法
- 96.不同的二叉搜索树
- 思路
- dp含义
- 递推公式
- 初始化
- 遍历顺序
- 打印
- CPP代码
- 题目总结
343.整数拆分
力扣题目链接
文章讲解:343.整数拆分
视频讲解:动态规划,本题关键在于理解递推公式!| LeetCode:343. 整数拆分
状态:哥们儿把从1-10的整数拆分全写出来了,思路嘎嘎有,要想乘积最大,必须把数字全部拆成2或者3。但是,如何跟动态规划联系起来呢?
看完题解出来了,哥们儿那个属于是数学方法,但是差很多完整的思考,后文会给予证明。
我认为本题更适合使用数学方法来解决,也就是数学归纳法
看到这个题目,会疑问应该拆成两个还是三个还是四个呢?
之前我们说过,动态规划用来解包含重叠子问题的某问题,那么这里直接试试动态规划。
思路
在之前你走过拆分2-10的流程吗,找到什么感觉了吗?当我们在拆10的时候,可能把10拆成4、6(或者是其他的什么),我们之前也拆过4和6,自然拆成2、2、3、3。发现了吗,我们拆10这个问题包含了重叠子问题(拆4和6),所以试试动态规划吧!
dp含义
自然一点的想法:
dp[i]
:拆分数字i
,可以得到的最大乘积为dp[i]
。
递推公式(难点)
递推公式的重难点是什么呢?先思考我们如何才能得到dp[i]
?
首先我们拆分i
,肯定首先拆成两个数字,也就是j
和(i - j)
。j
是遍历1
到j
的所有情况;
如果拆成3个数及3个数以上,我们就是j * dp[i - j]
,该式子的含义就是把i
拆成三个或三个以上数字(因为dp[i - j]包含了所有的拆分方法,且至少拆成两个
)
NOTE:
为什么公式
j * dp[i-j]
是成分成2个以上数字呢?首先我们要搞明白dp[i - j]的含义,拆分数字
i-j
,可以得到的最大乘积,他就暗含了将i-j
拆分成两个或两个以上数字。为什么
j
就不拆分了呢?由于我们是从1开始一直遍历到
j
,所以已经暗含了拆分j
的情况,因为我们还有旁边的dp[i-j]
来给j
补蛋呢!
综上所述, d p [ i ] = m a x ( d p [ i ] , m a x ( ( i − j ) ∗ j , d p [ i − j ] ∗ j ) ) dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)) dp[i]=max(dp[i],max((i−j)∗j,dp[i−j]∗j))
为什么这里多了个max(dp[i], ...)
呢?因为我们之前说过,我们需要遍历1~j
的数,所以为了保留每个i
当前最大成绩,与新遍历的j
上下文做比较,保持dp[i]
的最大值更新或者不更新。
初始化
本题中,我们只初始化dp[2]=1
,因为严格来说,dp[0] dp[1]
不应该初始化,因为这在我们定义dp数组含义时就确定了这俩是没有意义的数值,题中给定的n
也是大于等于2的。
遍历顺序
还记得上面我们说把1
遍历到j
不,这里我们需要两层遍历,对于dp
数组那肯定是从左到右了;关于j
应该是从1
开始,因为从0
开始仍然是没有意义的,难道我们还把一个数拆成0
和其他数吗?
for (int i = 3; i <= n; i++) {for (int j = 1; j < i - 1; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}
//再优化一下子
for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}
打印
CPP代码
class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1, 0);dp[2] = 1;for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};
数学方法
归纳证明法
我在写1-10的最优拆分方案过程中,确实感受到了以下规律,这里是leetcode的官解归纳证明法
- 第一步:证明最优的拆分方案中不会出现大于
4
的整数。
假设出现了大于 4 4 4 的整数 x x x,由于$ 2(x−2)>x 在 在 在x>4$时成立,将 x拆分成 2和 x−2可以增大乘积。因此最优的拆分方案中不会出现大于 4 的整数。
- 第二步:证明最优拆分方案中可以不出现整数4
很明显,出现4的话可以用 2 × 2 2 \times2 2×2代替
此时,可知最优的拆分方案只会出现1、2、3三个数字
- 第三步:证明 n ≥ 5 n \geq5 n≥5时,最优的拆分方案不会出现整数1.
当 n ≥ 5 n \geq5 n≥5时,如果出现了整数1,那么拆分中剩余的数的和为 n − 1 ≥ 4 n-1 \geq4 n−1≥4,对应这至少两个整数1和一个大于等于4的数。我们将其中任意一个整数 x x x加上1,乘积都会增大。
此时,可知当 n ≥ 5 n \geq5 n≥5时,最优拆分方案只有2和3
- 第三步:证明当 n ≥ 5 n \geq5 n≥5时,最优的拆分方案中2的个数不会超过3个
如果出现了超过 3 个 2,那么将它们转换成 2 个 3,可以增大乘积,即 3 × 3 > 2 × 2 × 2 3 \times 3 > 2 \times 2 \times 2 3×3>2×2×2
综上, n ≥ 5 n \geq5 n≥5的最优拆分方案就唯一了,这是因为当最优的拆分方案中2的个数分别为0,1,2个时,就对应着n除以3的余数分别为0,2,1的情况。
并且 n = 4 n = 4 n=4时的拆分方案也可以放入分类讨论的结果;当 2 ≤ n ≤ 3 2\leq n \leq3 2≤n≤3时,只有唯一的拆分方案 1 × ( n − 1 ) 1 \times (n - 1) 1×(n−1)
int integerBreak(int n) {int (n <= 3) {return n - 1;}int quotient = n / 3; //商int remainder = n % 3; //余数if (remainder == 0) { //能被3整除,全部拆成3return (int)pow(3, quotient);}else if (remainder == 1){ //余1return (int)pow(3, quotient - 1) * 4}else { //余2return (int)pow(3, quotient) * 2;}
}
96.不同的二叉搜索树
力扣题目链接
文章讲解:96.不同的二叉搜索树
视频讲解:动态规划找到子状态之间的关系很重要!| LeetCode:96.不同的二叉搜索树
状态:这个动态规划我知道!有点明显。dp数组肯定是1维的,含义就是组成的不同BST的个数,关于递推公式我列举了n等于1-4时各能组成多少个BST,在写4时发现了大致的规律,但是没能力抽象成数学公式
思路
直观上,我们肯定是要把n=1、2、3
直接拉出来比较的。
n=3
时,
- 当1为头结点,其右子树有两个结点,结点布局与
n=2
时一致 - 当2为头结点,其左右子树都只有一个结点,布局和
n=1
一致 - 当3位头结点,其左子树有两个节点,和
n=2
时一致
到这里我们就完全挖掘住了重叠的子问题。
dp[3] = 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是
dp[2]
。有1个元素的搜索树数量就是
dp[1]
。有0个元素的搜索树数量就是
dp[0]
。
综上 d p [ 3 ] = d p [ 2 ] ∗ d p [ 0 ] + d p [ 1 ] ∗ d p [ 1 ] + d p [ 0 ] ∗ d p [ 2 ] dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2] dp[3]=dp[2]∗dp[0]+dp[1]∗dp[1]+dp[0]∗dp[2].。
同理, d p [ 4 ] = d p [ 0 ] ∗ d p [ 3 ] + d p [ 1 ] ∗ d p [ 2 ] + d p [ 2 ] ∗ d p [ 1 ] + d p [ 3 ] ∗ d p [ 0 ] dp[4] = dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1]+ dp[3]*dp[0] dp[4]=dp[0]∗dp[3]+dp[1]∗dp[2]+dp[2]∗dp[1]+dp[3]∗dp[0],其中 d p [ 3 ] dp[3] dp[3]可以继续拆分,很显然我们的递推公式应该写成:
d p [ i ] = ∑ j = 1 i d p [ j − 1 ] d p [ i − j ] dp[i] = \sum_{j=1}^{i}dp[j-1]dp[i-j] dp[i]=∑j=1idp[j−1]dp[i−j],j-1
为j
为头结点左子树节点数量,i-j
为以j
为头结点右子树节点数量。很明显需要两个循环,一个大循环i
还有一个小循环j
dp含义
dp[i]
:表示的是i
个不同元素节点组成的二叉搜索树的个数为dp[i]
递推公式
上文分析中,已经给出了基本的递推公式
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j
相当于是头结点的元素,从1
遍历到i
为止。
所以递推公式:dp[i] += dp[j - 1] * dp[i - j]
; ,j-1
为j
为头结点左子树节点数量,i-j
为以j
为头结点右子树节点数量
初始化
从递推公式也可以看出来,本题其实只要初始化dp[0]
就可以了,他是推导的基础。
从定义上来讲,空结点也是一颗二叉树,也是一颗二叉搜索树。
综上:dp[0] = 1
遍历顺序
首先一定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]
可以看出,节点数为i
的状态是依靠i
之前节点数的状态。
那么遍历i
里面每一个数作为头结点的状态,用j
来遍历。
for (int i = 1; i <= n; i++){for (int j = 1; j <= i; i++) {dp[i] += dp[j - 1] * dp[i - j];}
}
打印
CPP代码
class Solution {
public:int numTrees(int n) {vector<int> dp(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];}
};
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
题目总结
本题我们用的是一种近似数学归纳法的推理。
在LeetCode官解中,给出了严格的数学证明,我认为这样的思考过程也是非常需要了解的。
-
LeetCode官解(必须手推一下!也不难!)
-
卡塔兰数:
- 卡塔兰数往往解决以下几类问题:
- 有效的括号组合的数量。
- 不同的二叉搜索树的数量。
- 凸多边形划分成三角形的方法数量。
- 在一个正方形格子图中从一角到另一角的路径数量,这些路径仅向上或向右移动,并且不越过对角线。
- 递推公式 C 0 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n C_0=1, C_{n+1}=\frac{2(2n+1)}{n+2}C_n C0=1,Cn+1=n+22(2n+1)Cn
- 卡塔兰数往往解决以下几类问题:
class Solution {
public:int numTrees(int n) {long long C = 1;for (int i = 0; i < n; ++i) {C = C * 2 * (2 * i + 1) / (i + 2);}return (int)C;}
};