代码随想录day40||● 343. 整数拆分 ● 96.不同的二叉搜索树

本文主要是介绍代码随想录day40||● 343. 整数拆分 ● 96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

343. 整数拆分 - 力扣（LeetCode）

动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[2]=1;for(int i=3;i<=n;i++)for(int j=1;j<=i/2;j++)//这里进行了减枝，具体知识为不等式a+b>=2*根号ab，当且a=b取得极值{dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));}return dp[n];}
};

96. 不同的二叉搜索树 - 力扣（LeetCode）

动态规划找到子状态之间的关系很重要！| LeetCode：96.不同的二叉搜索树_哔哩哔哩_bilibili

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1);dp[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
};

我们在求递推公式的时候（无头绪时）可以自己先手动模拟一下1、2、3的规律·

这篇关于代码随想录day40||● 343. 整数拆分 ● 96.不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---