本文主要是介绍代码随想录算法训练营day43 | 343. 整数拆分、96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
343. 整数拆分
- 确定dp数组以及下标的含义：dp[i]表示分拆数字i的最大乘积
- 确定递推公式：dp[i] = max(dp[i], max(i - k) * k, dp[i - k] * k});
- dp的初始化：dp[0]和dp[1]都是没有意义的，纯粹是为了后续遍历服务的
- 确定遍历顺序：从前向后遍历
- 举例推导dp数组
class Solution:def integerBreak(self, n: int) -> int:dp = [1] * (n+1)for i in range(2, n+1):for k in range(1, i):dp[i] = max(dp[i], max(k * dp[i-k], k * (i-k)))return dp[n]本题可以优化
因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。
例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。
只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。
那么 k 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。
class Solution:def integerBreak(self, n: int) -> int:dp = [1] * (n+1)dp[2] = 1for i in range(3, n+1):for k in range(1, i//2+1):dp[i] = max(dp[i], max(k * dp[i-k], k * (i-k)))return dp[n]96.不同的二叉搜索树
- 确定dp数组以及下标的含义：dp[i]表示由i个节点组成的二叉搜索树的种数
- 确定递推公式：dp[i] += dp[j - 1] * dp[i - j];
- dp数组的初始化：dp[0] = 1
- 确定遍历顺序：从前向后遍历
- 举例推导dp数组
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]这篇关于代码随想录算法训练营day43 | 343. 整数拆分、96.不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
