常州微网站建设,云南省网站备案,浙江十大外贸公司,校园生活网页设计【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96
需强化知识点
思路#xff1a;343 and 96
题目
343. 整数拆分
dp 含义#xff1a;拆分i#xff0c;乘积最大值#xff1b;依次遍历 i的因子#xff0c;记录最大值#xff0c;max#xff08;之前的…【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96
需强化知识点
思路343 and 96
题目
343. 整数拆分
dp 含义拆分i乘积最大值依次遍历 i的因子记录最大值max之前的因子两两拆分的情况多次拆分的情况
class Solution:def integerBreak(self, n: int) - int:# 拆分i乘积最大值dp [1] * (n1)for i in range(2, n1):for j in range(1, i1):dp[i] max(max( j * (i-j), dp[j] * (i-j)), dp[i])return dp[n]96. 不同的二叉搜索树
代码随想录思路dp 的含义1到i为节点组成的二叉搜索树的个数为dp[i]递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为 j 为头结点左子树节点数量i-j 为以 j 为头结点右子树节点数量依次累加此处只需要考虑种类数因此可以直接使用dp[i - j], 因为数字的大小排序情况是等价的注意初始值的赋予因为此处是累加不能都赋值为1
class Solution:def numTrees(self, n: int) - int:# 1到i为节点组成的二叉搜索树的个数为dp[i]。dp [0] * (n 1)dp[0], dp[1] 1, 1for i in range(2, n1):for j in range(1, i1):dp[i] dp[j-1] * dp[i-j]return dp[n]
