代码随想录算法训练营 Day41 动态规划3

Day41 动态规划3

343. 整数拆分

思路

不知道如何拆分，才能使乘积最大化
有什么理论依据？

根据代码随想录
拆分使乘积最大化逻辑：应该尽可能拆成相同的数

根据题目，发现，拆分后的数可以继续拆分，因此可以用动规的思路

要点：

1. dp数组含义 对i进行拆分，得到最大乘积为dp[i]
2. 递推公式：
   如果拆成两个数：j * (i - j)
   如果拆成三个数以上：j * dp[i - j]
   递推公式可以将所有的情况都考虑，在比较取最大值就行；因此不知道上述逻辑也能写

最终代码：

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 0
        dp[2] = 1
        for 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可以根据0，1，2三种情况推导出来

j 为根节点，左边有j - 1个节点，右面有i - j个节点

最终代码：

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[n]

总结
这题有点难，没做过想不到怎么做