343. 整数拆分
https://leetcode.cn/problems/integer-break/
算法思想：
dp[i] 对i进行拆分，获得最大的乘积
递推公式：
情况1：
dp[i] = j *dp[i-j]
j可以从1开始枚举，固定j不变，变化i-j的结果取得最大乘积
dp[i-j] != i-j
最后的递归公式是：
dp[i] = max(j * dp[i-j], j*(i-j))
j遍历取最大值。
因为最大的乘积因子肯定是近似的，因此j遍历到i/2就可以了
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1, 0);
dp[0]=0;
dp[1] =0;
dp[2] = 1;
for(int i = 3;i<=n;i++ )
{
for(int j=1;j<=i/2;j++)
{
dp[i] = max(dp[i], max(j * dp[i-j], j* (i-j)));
}
}
return dp[n];
}
};
96. 不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/
算法思想：
dp[n]表示n个节点组成的二叉搜索树共有dp[i]个。
可以枚举根节点的值，当根节点是从1-n时的情况。
dp[n]为枚举的结果的和。
递推公式：
dp[n] = dp[j-1]* dp[i-j]
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
};
