动态规划part03 343. 整数拆分 96. 不同的二叉搜索树
343. 整数拆分
动规五部曲:
1.确定dp数组以及下标的含义
dp[i]含义为:对i进行整数拆分,最大乘积是dp[i]
2.确定递推公式
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
3.dp数组如何初始化
dp[0] = 0; dp[1] = 0; dp[2] = 1;
4.确定遍历顺序
顺序遍历
5.举例推导dp数组
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[2] = 1;
for(int i = 3; i<dp.size();i++){
for(int j = 1 ; j<=i/2;j++){
dp[i] = max(dp[i],max((i-j)*j,dp[i-j]*j));
}
}
return dp[n];
}
};
另一种方法:
本题也可以用贪心,每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!
class Solution {
public:
int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int result = 1;
while (n > 4) {
result *= 3;
n -= 3;
}
result *= n;
return result;
}
};
96. 不同的二叉搜索树
动规五部曲:
1.确定dp数组以及下标的含义
dp[i]含义为:输入i个节点,二叉搜索树可能的种数
2.确定递推公式
dp[i] += dp[j - 1] * dp[i - j];
3.dp数组如何初始化
dp[1] = 1; dp[2] = 2; dp[3] = 5;
![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=…%2FAppData%2FRoaming%2FTypora%2Ftypora-user-images%2Fimage-20240122171917362.png&pos_id=img-P7LgrpPx-1705915671995
4.确定遍历顺序
for(int i =1;i<=n;i++){ //dp[i]需要前一个数值为基础进行运算,顺序遍历
for(int j =1; j<=i;j++){ //遍历i里面每一个数作为头结点的状态,用j来遍历。
dp[i] += dp[j - 1] * dp[i - j]
}
}
5.举例推导dp数组
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];
}
};