沈阳专业网站建设企业,成都哪里好玩好吃,wordpress美化底部,网站建设的讲话稿Leetcode 343. 整数拆分
讲解前#xff1a;
毫无头绪
讲解后#xff1a;
这道题的动态思路一开始很不容易想出来#xff0c;虽然dp数组的定义如果知道是动态规划的话估摸着可以想出来那就是很straight forward dp定义#xff1a;一维数组dp[i], i 代表整数的值#xf…Leetcode 343. 整数拆分
讲解前
毫无头绪
讲解后
这道题的动态思路一开始很不容易想出来虽然dp数组的定义如果知道是动态规划的话估摸着可以想出来那就是很straight forward dp定义一维数组dp[i], i 代表整数的值dp[i] 代表将整数 i 拆分的话可以获得的最大乘积 然后呢就是定义递归推导式了我们可以这样去想这道题既然题目要求我们拆分的话必须要最少有两个数那么其实可以把获得最大乘积的可能分为两种情况对于每一个整数 i我们进行一个遍历让 j 从 1 遍历到 i - 1也就是当 i 5的时候j遍历1,2,3,4 这样的话相当于我们可以找到拆分成两个数的所有可能那么第一种情况就是 最大的乘积是从 j * (i - j) 中获取的也就是1*4, 2*3, 3* 2, 4*1, 第二种情况就会变成最大乘积是从3个以上的数字中获得的意味着我们会对 i - j 遍历到的数字进行拆分那么如果我们刚好能得到 拆分 j - i 的乘积最大值那么再和 j 相乘一定就也是当我们用三个以上数字的最大乘积那拆分 j 的乘积最大值是多少呢不就刚好是 dp[i - j] 吗下面我画了当 i 是3,4,5 的时候我们会计算的所有值 你会发现这样的话对于三个数以上的可能我们也完全不用担心会错过一些组合由于动态递归的帮助我们在计算出一个dp[i] 的值之前就已经考虑过了所有的可能
这里还要注意一点, 以上的计算只是在当整数是 i 的时候我们在比较到底是当我们之后 j * (i - j)两个数相乘的时候有更大乘积还是当我们有 j * 拆分(j - i) 一共三个数以上的时候有更大的乘积但是我们并不知道当 j 遍历到哪的时候会得到所有可能中最大的乘积所以在推导式中还要再加入一个比较就是一直更新保持dp[i] 储存遍历过程中最大的值
那么我们就可以总结出来递归推导公式 dp[i] max(dp[i], max(j * (i - j), j * dp[i - j])) class Solution:def integerBreak(self, n: int) - int:dp [0] * (n 1)dp[2] 1for i in range(3, n 1):for j in range(1, i):dp[i] max(dp[i], max(j * (i - j), j * dp[i - j]))print(dp)return dp[n] Leetcode 96. 不同的二叉搜索树
讲解前
太难了
讲解后
这道题首先我们可以把从n1到n3的所有可能画出来 观察上面的图仔细去看其中的规律我们其实可以总结出来两个非常重要的点来帮助我们推导我们的dp推导公式
1. 对于任何n个节点从1到n不相同的平衡二叉树其实所有的组合是首先我们把1作为root节点找到有多少种组合然后再把2作为头节点然后去找有多少组合再把3作为头节点去找有多少种组合.......直到把n作为头节点看有多少组合然后全部加起来就如上图的n3答案52(1 as root) 1(2 as root) 2(3 as root) 个组合
2. 对于二叉树来说如果我们能够知道左子树一共有多少种组合并且直到右子树一共有多少种组合那么其实这个二叉树一共就有左子树组合数 * 右子树组合数 数量的组合因为每一个特别的左子树都可以和每一个特别的右子树结合来构造一个新的树举个例子的话就是上图中的在n3并且我们的root是1的时候我们有两种组合其实这两种组合是这样得来的我们知道root1的时候左子树没有节点的时候有一个可能就是空也就是左子树的组合数为1然后呢右子树的话由2和3两个节点组成他们有两种可能分别是让3在2的右节点或者2在3的左节点这样以来我们就知道对于root1的时候我们一共有1*22种组合
有了上面两个概念首先我们可以把动态规划数组的含义想出来还是很简单直接按照题意来写 dp[i], i是n也就是当我们的二叉平衡树是由1-n节点组成的dp[i] 储存的值就是有多少种不同的可能来构建这个二叉平衡树 接下来我们可以去想那既然我们知道了上面的概念那么我们首先可以确定在每一个dp[i] 求值的过程中我们需要进行一个叠加这个叠加就是概念1就是用 j 来从1-n遍历找到当 j 为root的时候每个二叉树分别有多少种构造方法那这个该怎么找呢我们发现当我们知道rootj 的时候其实左右两个节点分别含有多少节点我们是知道的因为我们知道一共有1-n个节点并且没有重复那假设我们有1-10个节点如果root取7我们就知道那左子树一定有6个节点分别是1-6然后右子树有3个节点是8,9,10这是用 j - 1和i - j 得来的那这不就方便了吗通过概念2我们知道不同二叉树的数量就等于左子树的变化数量 * 右子树的变化数量我们还知道左子树的节点数量和右子树的节点数量知道了节点数量找变化数量不就是我们dp数组的含义吗所以这个时候我们就可以先按照上图中的n3的情况写一下这个答案5是怎么得来的
dp[3] dp[0] * dp[2] (root1) dp[1] * dp[1] (root2) dp[2] * dp[0] (root3)这样以来我们就可以推导出公式了 j 为root的元素然后从 1 遍历到 i, 然后dp[i] 的值做一个叠加分别是j不同值的答案总和 dp[i] dp[i] dp[j - 1] * dp[i - j] dp推导公式搞明白之后代码就不难了遍历顺序就是正常的从左到右我们要先知道小的n才能推理出后面的n然后呢初始化就是没有节点和就一个节点的组合数量都是1, dp[0] 1, dp[1] 1
class Solution:def numTrees(self, n: int) - int:# initialize the dp array # have it set to length of n 1 cuz the answer is dp[n]dp [0] * (n 1)# we know only 1 possibility for n 0 and 1dp[0], dp[1] 1, 1# start iteration from when we have 2 nodesfor i in range(2, n 1):for j in range(1, i 1):dp[i] dp[i] dp[j - 1] * dp[i - j]return dp[n]
