旅游公司网站开发,用dw做的网页怎么连到网站上,东阳网站建设yw81,淘宝官网首页手机版Day41 动态规划3
343. 整数拆分
思路
不知道如何拆分#xff0c;才能使乘积最大化 有什么理论依据#xff1f;
根据代码随想录 拆分使乘积最大化逻辑#xff1a;应该尽可能拆成相同的数
根据题目#xff0c;发现#xff0c;拆分后的数可以继续拆分#xff0c;因此可…Day41 动态规划3
343. 整数拆分
思路
不知道如何拆分才能使乘积最大化 有什么理论依据
根据代码随想录 拆分使乘积最大化逻辑应该尽可能拆成相同的数
根据题目发现拆分后的数可以继续拆分因此可以用动规的思路
要点
dp数组含义 对i进行拆分得到最大乘积为dp[i]递推公式 如果拆成两个数j * (i - j) 如果拆成三个数以上j * dp[i - j] 递推公式可以将所有的情况都考虑在比较取最大值就行因此不知道上述逻辑也能写
最终代码
class Solution:def integerBreak(self, n: int) - int:dp [0] * (n 1)dp[0] 0dp[1] 0dp[2] 1for i in range(3, n 1):for j in range(1, i // 2 1):dp[i] max(j * (i - j), j * dp[i - j], dp[i])return dp[n]总结 一开始不知道怎么拆最大觉得会有一个特别的逻辑但是实际写代码的时候是一个暴力的方式将所有的情况都考虑再比较取值的。
96.不同的二叉搜索树
思路
dp[i]的结果可以看作根节点为1到i的二叉搜索树种数之和 但是不同n根节点为i得到的结果也不同 不知道怎么想递推公式
根据代码随想录 首先根据样例观察规律 n 3 1为根节点以及3为根节点右子树的分布和n为2的布局是一样的 2为根节点左右子树的分布根n为1一样
总共和 根节点为1的情况 根节点为2 根节点为3 根节点为1 左子树0个节点 * 右子树2个节点 根2 左子树1个节点 * 右子树1个节点 根3 左子树2个节点 * 右子树0个节点
n 3可以根据012三种情况推导出来
j 为根节点左边有j - 1个节点右面有i - j个节点
最终代码
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]总结 这题有点难没做过想不到怎么做
