【代码随想录训练营】【Day 43】【动态规划-3】| Leetcode 343, 96

• dp 含义：拆分i，乘积最大值；依次遍历 i的因子，记录最大值，max（之前的因子，两两拆分的情况，多次拆分的情况）

class Solution:def integerBreak(self, n: int) -> int:# 拆分i，乘积最大值dp = [1] * (n+1)for i in range(2, n+1):for j in range(1, i+1):dp[i] = max(max( j * (i-j), dp[j] * (i-j)), dp[i])return dp[n]

• 代码随想录思路
• 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, n+1):for j in range(1, i+1):dp[i] += dp[j-1] * dp[i-j]return dp[n]