343. 整數(shù)拆分
https://leetcode.cn/problems/integer-break/
算法思想：
dp[i] 對i進行拆分，獲得最大的乘積
遞推公式：
情況1：
dp[i] = j *dp[i-j]
j可以從1開始枚舉，固定j不變，變化i-j的結(jié)果取得最大乘積
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個節(jié)點組成的二叉搜索樹共有dp[i]個。
可以枚舉根節(jié)點的值，當根節(jié)點是從1-n時的情況。
dp[n]為枚舉的結(jié)果的和。
遞推公式：
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];
? ? }
};
