本文主要是介绍算法训练营Day41（动态规划3），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
说明
今天两题都挺有难度，建议大家思考一下没思路，直接看题解，第一次做，硬想很难想出来。
343. 整数拆分 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution:# 假设对正整数 i 拆分出的第一个正整数是 j（1 <= j < i），则有以下两种方案：# 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)# 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]def integerBreak(self, n):dp = [0] * (n + 1) # 创建一个大小为n+1的数组来存储计算结果dp[2] = 1 # 初始化dp[2]为1，因为当n=2时，只有一个切割方式1+1=2，乘积为1# 从3开始计算，直到nfor i in range(3, n + 1):# 遍历所有可能的切割点for j in range(1, i // 2 + 1):# 计算切割点j和剩余部分(i-j)的乘积，并与之前的结果进行比较取较大值dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)return dp[n] # 返回最终的计算结果疑惑
递推公式为什么里面要加 d[i]
96.不同的二叉搜索树 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution:def numTrees(self, n: int) -> int:dp = [0] * (n + 1) # 创建一个长度为n+1的数组，初始化为0dp[0] = 1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1for i in range(1, n + 1): # 遍历从1到n的每个数字for j in range(1, i + 1): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量dp[i] += dp[j - 1] * dp[i - j] # 利用动态规划的思想，累加左子树和右子树的组合数量return dp[n] # 返回以1到n为节点的二叉搜索树的总数量这篇关于算法训练营Day41（动态规划3）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
