微商城手机网站制作,标志设计公司成都,湖北省节能建设网站,搜索引擎优化关键字*343. 整数拆分
https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html 视频讲解#xff1a;https://www.bilibili.com/video/BV1Mg411q7YJ
考点 动态规划 我的思路 无思路 视频讲解关键点总结 怎么想到动态规划的#xff1f;一个数可以拆成两个数https://www.bilibili.com/video/BV1Mg411q7YJ
考点 动态规划 我的思路 无思路 视频讲解关键点总结 怎么想到动态规划的一个数可以拆成两个数也可以拆成多个数如果拆成多个数相当于先拆出来的两个数中有一个应该继续拆下去这时候就可以用到动态规划了因为那个继续拆的数字能拆出来的最大乘积可以通过dp数组的遍历在之前得到动规五部曲 dp数组的每个位置 i 对应数字 i 经拆分后能得到的最大乘积递推公式取以下三种情况里的最大值作为当前dp值 把当前数拆成两个数字的乘积把当前数拆成多个数字的乘积初始拆成两个数选其中一个数取其dp值即相当于对其进行了进一步拆分并获取到最大乘积当前dp值 初始化 dp[0]和dp[1]其实不能拆分所以初始化为0dp[2]可拆分初始化为1之后从dp[3]开始使用动态规划递推 从前向后遍历双层for循环外层负责遍历dp内层负责遍历当前 i 拆成两个数的所有情况不需要打印 我的思路的问题 无思路 代码书写问题 无 可执行代码
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(j * (i - j), j * dp[i - j], dp[i])return dp[-1]*96.不同的二叉搜索树
https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html 视屏讲解https://www.bilibili.com/video/BV1eK411o7QA
考点 动态规划 我的思路 无思路 视频讲解关键点总结 二叉树的题还是要画图分析以n为3为例进行分析所有的二叉搜索树结果分为以1为根节点、2为根节点和3为根节点的情况 1为根节点左子树只有1种情况即空树右子树有2/3两个子节点组合为两种情况2为根节点左子树有一种情况1右子树有一种情况33为根节点左子树有1/2两个子节点组合为两种情况右子树有一种情况即空树 分析可发现由于二叉搜索树的性质其左子树和右子树的情况可以通过比n小的情况时的二叉搜索树数量递推得到dp数组第 i 个元素代表n为 i 的时候共有多少种可能的二叉搜索树递推公式为循环遍历从1为根节点到n为根节点的情况并对遍历到 j 时令dp[n] dp[j - 1] * dp[n - j] 这里右子树直接去n-j对应的dp值是因为树有多少种可能的结构与递增数组的具体值无关只与其数的个数有关因此可以如此操作将dp[0]初始化为1代表空树的情况共有一种双重循环均从前向后遍历无需打印 我的思路的问题 无思路 代码书写问题 无 可执行代码
class Solution:def numTrees(self, n: int) - int:dp [0] * (n 1)dp[0] 1for i in range(1, n 1):for j in range(1, i 1):dp[i] dp[j - 1] * dp[i - j]return dp[n]
