浙江网站建设和制作,品牌网站建设顾问,现代建筑风格特点,企业网站建立哪343.整数拆分
思路#xff1a;
1.dp存储的是第i个数#xff0c;拆分之后最大乘积2.dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));3.初始化#xff1a;dp[0]dp[1]0,dp[2]1;4.遍历顺序#xff1a;外层循环 3-n#xff0c;内层循环 1-i
2.涉及两次取max#xff1a;
dp[i] 表…343.整数拆分
思路
1.dp存储的是第i个数拆分之后最大乘积2.dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));3.初始化dp[0]dp[1]0,dp[2]1;4.遍历顺序外层循环 3-n内层循环 1-i
2.涉及两次取max
dp[i] 表示拆开的最大乘积因为涉及多次计算j*(i-j) 表示拆成两个数j*dp[i-j] 表示拆成两个以上的数dp[i-j] 就是剩下没拆的数拆开的最大乘积
class Solution {
public:int integerBreak(int n) {vectorintdp(n1,0);dp[2]1;for(int i3;in;i){for(int j1;ji;j){dp[i]max(dp[i],max(j*(i-j),j*dp[i-j]));couti dp[i]endl;}}return dp[n];}
}; 96.不同的二叉搜索树
分析1-n有几种二叉搜索树 1.以1-n每个数为根节点 2.判断根节点左边和右边各有几个节点只有结点数相同组合的二叉搜索树种数就是一样的。
思路
1.dp存储n个节点有多少种二叉搜索树2.dp[i]dp[i-1]*dp[n-i];3.初始化dp[0]dp[1]1,dp[2]2;4.遍历顺序3-n 416.分割等和子集
分析
数组要求分成两个等和子集所以一定要有子集和为总和的一半转换为在集合中找数字看能否组合成总和的一半值的子集转换为在总和一半容量的背包里寻找子集刚好装满
思路一
1.dp存储容量为 j 时装入物品的最大值
2.dp [ j ] max ( dp [ j ] ,dp [ j - nums [i] ] nums [ i ] )
3.初始化所有值初始化为0
4.遍历顺序:外层遍历数字顺序物品内层遍历数字倒序背包容量
class Solution {
public:bool canPartition(vectorint nums) {int total0;for(auto it:nums) totalit;//求出总和if(total%2!0) return false;//过滤不可拆成两半的情况int targettotal/2;//背包容量vectorintdp(10001,0);for(int i0;inums.size();i){//遍历物品for(int jtarget;jnums[i];j--){//背包容量递减最少能装入一个物品dp[j]max(dp[j],dp[j-nums[i]]nums[i]);//dp[j] 是不装当前物品//dp[j-nums[i]]nums[i] 是装当前物品}}if(dp[target]target) return true;//背包容量为target装了target重的物品return false;}
};
