本文主要是介绍@ 代码随想录算法训练营第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为根节点,左右两边不同布局相乘,再依次相加。
这篇关于@ 代码随想录算法训练营第7周(C语言)|Day41(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!