做网站有什么不好,潍坊网站设计制作,网站设计案例公司,湖北广域建设管理有限公司网站题目1#xff1a;343 整数拆分
题目链接#xff1a;整数拆分
对题目的理解
将正整数n#xff0c;拆分成k个正整数的和#xff08;k2#xff09;使得这些整数的乘积最大化#xff0c;返回最大乘积
动规五部曲
1#xff09;dp数组的含义以及其下标i的含义
dp[i]…题目1343 整数拆分
题目链接整数拆分
对题目的理解
将正整数n拆分成k个正整数的和k2使得这些整数的乘积最大化返回最大乘积
动规五部曲
1dp数组的含义以及其下标i的含义
dp[i]对 i 进行拆分得到最大的乘积为dp[i]
2递推公式
dp[i] j*(i-j) 将i拆分成2个数j和-j
dp[i] j*dp[i-j] 将i拆分成3个或3个以上的数
因为要求的是最大乘积所以递推公式为dp[i]max(j*(i-j)j*dp[i-j]dp[i])
3dp数组初始化
dp[0] 0 0只能拆成00而题目要求至少拆分成两个正整数的和所以初始化dp[0]没有意义
dp[1] 0 1只能拆成01而题目要求至少拆分成两个正整数的和所以初始化dp[1]没有意义
dp[2] 1 只能拆分成11是两个正整数
所以只初始化dp[2]就ok
4遍历顺序
dp[i]根据dp[i-j]所以i一定是从前向后遍历且i是从3开始遍历j是从1开始遍历因为i-j2
5打印dp数组
代码
class Solution {
public:int integerBreak(int n) {//定义dp数组int dp[n1];//初始化dp数组dp[2]1;//递推for(int i3;in;i){for(int j1;ji;j){dp[i]max(max(j*(i-j),j*dp[i-j]),dp[i]);}}return dp[n];}
};
这段代码会报错 报错的原因是因为dp数组使用int直接定义不会内部初始化为0而是任意值所以造成这种超时错误所以需要使用vector进行数组的定义使用vector会默认将数组的元素定义为0
将代码改正使用vector定义
class Solution {
public:int integerBreak(int n) {//定义dp数组vectorint dp(n1);//初始化dp数组dp[2]1;//递推for(int i3;in;i){for(int j1;ji;j){dp[i]max(max(j*(i-j),j*dp[i-j]),dp[i]);}}return dp[n];}
};
时间复杂度O(n^2)空间复杂度O(n)
题目296 不同的二叉搜索树
题目链接不同的二叉搜索树
对题目的理解
由n个节点组成节点值从1到n互不相同的二叉搜索树有多少种
首先明确二叉搜索树长什么样
二叉搜索树是一个有序树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树 从图中可以看出n为3时当根节点为1和3时它的左右子树布局与n为2时相同只是数值不同而已当根节点为2时它的左右子树的布局与n为1时相同因此找到了内部推导关系
动规五部曲
1dp数组的含义以及下标i的含义
dp[i]:节点值从1到i的二叉搜索树的种类
2递推公式
以j为头节点j会枚举头节点从1到i那么以j为头节点的左子树就是j-1右子树就是i-j
dp[i] dp[j-1] * dp[i-j]dp[i]收录节点i的所有情况节点值从1到i二叉树的种类
3dp数组初始化
dp[0]1,空子树也是一种二叉搜索树
4遍历顺序
根据递推公式dp[i] dp[j-1] * dp[i-j]节点i的二叉搜索树种类都是依靠其之前的节点确定的所以节点要从小到大遍历
5打印dp数组
代码
class Solution {
public:int numTrees(int n) {//定义dp数组vectorint dp(n1);//初始化dp数组dp[0] 1;//递推for(int i1;in;i){//因为节点值从1到n,每一个值都要作为根节点都是一类情况for(int j1;ji;j){//j枚举所有从1到i所有头节点的情况dp[i]dp[j-1]*dp[i-j];//左子树是j-1个节点右子树是i-j个节点}}return dp[n];}
};
时间复杂度O(n^2)空间复杂度O(n)
