转播网站如何做,柳州论坛网站建设,wordpress 邮箱验证码,火车头wordpress发布模块#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 整数拆分不同的二叉搜索树总… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 整数拆分不同的二叉搜索树总结 本期的两道题都有一些难度不同的是第一道题看着可能有点想法但是就是感觉差一点思路以及代码不好实现第二道题压根没什么思路想不到它到底和动态规划的关系在哪这是我对于初次做这两道题时候的想法。
整数拆分
343. 整数拆分 - 力扣LeetCode
整数拆分在leetcode上是一道中等难度的题它的题目大意是将给定整数n拆解成若干数字乘积的形式然后求出这些乘积中最大的一项是多少。我们首先要保证拆解出来的数字相加和应当等于原来的整数n。起初在做题的时候我仅能想到用一个dp数组且数组内部存取的应当是某个数字的最大乘积进而一步步推出n的最大乘积但是剩余的部分想不明白。我们来一起看看题解的解释根据题解的思路来一步步推出。
dp数组的含义dp数组含义之前已经说过了它实际上就是求出第i个数字能够分解出来的数的乘积的最大值。
递推公式这道题是将一个数字n分解成若干数字然后求最大乘积的题那么有人就要问了那我们为什么还要用数组保存1-n的全部数字的整数拆分呢关键点就在这里我们要将该数分解就要知道我们是怎么分解的一个数可以被分解为j*i-jj是从1到i的数例如说分解4我们可以将其分解为14223141这么四种也就是刚才的那个公式j在循环里不断地增大这样我么就可以使其算式发生变化。那么之前也说过不一定将n这个整数分解成两个数相乘的形式只要分解出的数相加等于n那么可以一直分解例如10这个数我们可以分解为334这也是合法的那如果分解成这样我们要如何表示呢这也是很重要的一点我们可以想象334是由4乘上9得到的根据dp数组的记忆我们可以写成是4*dp【9】这是没毛病的因为dp数组的定义就是某个数能被拆分后的最大乘积值所以我们可以根据用dp数组来完成对于多个数字的拆分。 关于j的拆分 我们之前的上面写的公式都是假定j是根据循环变化而变化的值而不是在递推公式里直接参与拆分的那我们是否会落下一些情况呢实际上并不会每一次的j的变化而引起的数字拆分是由上向下产生影响的例如说10可以拆分为22222那除了第一个2代表j之外其余的2也可以分成11但是不要忘记第一个2也就是j的位置早在前面j1时候已经被拆成过11了所以我们完全不要担心后面能举出的j的拆分实例均在j变得更小的时候完成过类似于拆分的乘积运算了。
下一个我们需要在意的点是由于递推公式写在j的变化之时所以dp【i】是一定会随着j而改变的那如果dp【i】之前已经找到了最大的值我们还让他不停赋新值不是会错过了吗所以我们取一个最大值即在dp【i】和j*i-j和j*dp【i-j}这三个值之中取出最大值赋给dp【i】以达到保存更新最大值的效用。
dp数组的初始化初始化就是dp【2】2为什么要这么写因为0和1不能拆分0就不用说了1无法拆分成两个整数的相加。
遍历顺序递推公式就可以得知了我们推出当前的数字i的最大乘积完全依赖于之前的数字所以我们要从前向后遍历。
class Solution {
public:int integerBreak(int n) {vectorintdp(n1,0);dp[2]1;for(int i3;in;i){for(int j1;ji;j)dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));//dp[i-j]就相当于对i-j的拆分了}return dp[n];}
};代码还是很简单的但是想出思路要注意的点还是蛮多的。
拆分的策略实际上就是固定前面的数字j不拆分j而通过对于j的增加而改变后面要拆分的值的策略。
不同的二叉搜索树
96. 不同的二叉搜索树 - 力扣LeetCode
这道题是很难的可以说是困难题了。首先一定要审好题这是一个求不同的二叉搜索树的题是二叉搜索树而不是别的什么强调这一点是因为二叉搜索树是有一定的规律的。
这道题为什么说它难呢递推公式比上一道题还难想我们是根据分别列出n1n2和n3三种情况的二叉搜索树的形状来找出一定的规律。n1只有一种情况就是一个节点n2是一个八字形即1开头的话那么就是有右子树22开头的话就是有一个左子树1没有其他情况因为这是搜索树要严格按照搜索树的特点。n3就分为1开头2开头和3开头三种情况其中画图可知1和3开头的情况是和n2的情况是一样的两个八字形而n以2开头是和n1情况一样是左右子树都平均的情况。这样算下来确实和题目案例对上了n3时候有五种情况而这里我们是考虑二叉树的形状而非二叉树节点值的不同所以我们将n3的以各个数字开头的情况和n1和n2的情况做了类比。
dp数组的含义这里我们明确dp数组的含义实际上是用来保存数值i有多少种不同的二叉树。 递推公式 我们在上面已经分析了很多了这里再来好好的看看递推公式的规律。 n3的情况就是元素以1开头情况加上以2开头加上以3开头的情况。
而以1开头数量实际上等于右子树的有两个元素的情况*左子树有0个元素都情况
以2开头的数量等于右子树有一个元素的情况*左子树有1个元素的情况
以3开头的数量等于右子树有0个元素的情况*左子树有两个元素的情况
那么为什么是以乘法的形式得出的呢而不是加法我们假设左子树有五种元素情况右子树有十种那是不是左子树的每一种和右子树的十种都可以构造出不同的情况呢所以我们这里用的公式就一定是乘法。
而有两个元素的情况就是n2也就是dp【2】有1个就是dp【1】0个就是dp【0】这里看不懂需要回想dp数组的含义是什么
知道了这样的一个规律后我们就可以推出dp【i】dp【j-1】*dp【i-j】
j-1是求左子树i-j是求右子树这里如果想不明白可以用n3的各种情况带入就能证明该公式一定是对的那么为什么是而不是等于呢这是因为我们要将各个情况都加进去也就是1-n的所有开头情况加在一起才是为n时的总二叉树个数。
dp初始化dp的初始化就仅仅将dp【0】1就可以了。0个节点也属于一种二叉树的情况。根据0
进而推出123等等。
遍历顺序很明显也是一道从前往后遍历因为要知道前面的情况才能得出n的情况。
class Solution {
public:int numTrees(int n) {vectorintdp(n1);dp[0]1;for(int i1;in;i){for(int j1;ji;j)dp[i]dp[j-1]*dp[i-j];}return dp[n];}
};这就是本题的代码了。虽然本题代码很简短但是代码很难想出。
首先能想到用动态规划做就有点难度其次是规律十分难找我们要能想出用前面的情况推出此时以1-n开头的各顶点情况能与之前的1到n-1的各种情况相呼应是很难的再其次我们用以表示左右二叉树的j-1和i-j这也是很难想出来的可能需要一定的数学推理。这些条件都使这道题变得毫无头绪不知道入手点在哪里自然就做不出来。
总结
今天我们完成了整数拆分不同的二叉搜索树两道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
