@ 代码随想录算法训练营第7周（C语言）|Day41（动态规划）
@ 代码随想录算法训练营第7周（C语言）|Day41（动态规划）
Day41、动态规划（包含题目 ● 343. 整数拆分 ● 96.不同的二叉搜索树 ）
343. 整数拆分
题目描述
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
题目解答
int max(int a,int b ,int c){
int res;
res=a>b?a:b;
res=res>c?res:c;
return res;
}
int integerBreak(int n) {
int bp[n+1];
for(int i=0;i<=n;i++){
bp[i]=0;
}
//需要这样 不然会出错
bp[2]=1;
for(int i=3;i<=n;i++){
for(int j=1;j<i-1;j++){
bp[i]=max(bp[i],j*(i-j),j*bp[i-j]);
}
}
return bp[n];
}
题目总结
递推公式很难想到，n平方的时间复杂度，与下面的题目相似。
96.不同的二叉搜索树
题目描述
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
题目解答
int numTrees(int n) {
int dp[n+1];
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=0;
}
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];
}
题目总结
从以一为根节点到一i为根节点，左右两边不同布局相乘，再依次相加。