外贸网站建设深圳,东莞南海网站制作,简述企业网站的基本功能,如何本地搭建自己的网站算法学习——LeetCode力扣动态规划篇2 343. 整数拆分
343. 整数拆分 - 力扣#xff08;LeetCode#xff09;
描述
给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。
返回 你可以获得…算法学习——LeetCode力扣动态规划篇2 343. 整数拆分
343. 整数拆分 - 力扣LeetCode
描述
给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例
示例 1:
输入: n 2 输出: 1 解释: 2 1 1, 1 × 1 1。
示例 2:
输入: n 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36。
提示
2 n 58
代码解析
dp[i]分拆数字i可以得到的最大乘积为dp[i]。
确定递推公式 可以想 dp[i]最大乘积是怎么得到的呢
其实可以从1遍历j然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。 一个是j * dp[i - j]相当于是拆分(i - j)对这个拆分不理解的话可以回想dp数组的定义。
也可以这么理解j * (i - j) 是单纯的把整数拆分为两个数相乘而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
所以递推公式dp[i] max({dp[i], (i - j) * j, dp[i - j] * j});
那么在取最大值的时候为什么还要比较dp[i]呢
因为在递推公式推导的过程中每次计算dp[i]取最大的而已。
class Solution {
public:int integerBreak(int n) {vectorint dp(n1,0);dp[2] 1 ; for(int i3 ; in;i){//计算i的分割点j从1开始分割到i-1for(int j1 ; ji ;j){//找到最大乘积的时候dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));couti:i dp:dp[i]endl;}}return dp[n];}
};
96. 不同的二叉搜索树
96. 不同的二叉搜索树 - 力扣LeetCode
描述
给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 示例
示例 1
输入n 3 输出5
示例 2
输入n 1 输出1
提示
1 n 19
代码描述
当3为头结点的时候其左子树有两个节点看这两个节点的布局是不是和n为2的时候两棵树的布局也是一样的啊
当2为头结点的时候其左右子树都只有一个节点布局是不是和n为1的时候只有一棵树的布局也是一样的啊
dp[3]就是 元素1为头结点搜索树的数量 元素2为头结点搜索树的数量 元素3为头结点搜索树的数量 元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
所以dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]
动态规划
确定递推公式 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素从1遍历到i为止。
所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量
dp数组如何初始化
从定义上来讲空节点也是一棵二叉树也是一棵二叉搜索树这是可以说得通的。
j为头结点左子树节点数量为0也需要dp[以j为头结点左子树节点数量] 1 否则乘法的结果就都变成0了。 所以初始化dp[0] 1
class Solution {
public:int numTrees(int n) {if(n2) return n;vectorint dp(n1,0);dp[0] 1;dp[1] 1;dp[2] 2;for(int i3 ; in ;i){for(int j1 ; ji ;j){dp[i] dp[j-1] * dp[i-j];}}return dp[n];}
};
416. 分割等和子集
416. 分割等和子集 - 力扣LeetCode
描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例
示例 1
输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。
提示
1 nums.length 200 1 nums[i] 100
代码解析
一个商品如果可以重复多次放入是完全背包而只能放入一次是01背包写法还是不一样的。 本题中使用的是01背包因为元素我们只能用一次。
背包的体积为sum / 2背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
动态背包二维背包
dp[ i ][ j ] 中
i 是放入背包中元素的范围从0 - i 中取元素每个元素取一次。j 是当前背包的容量上限 本题的核心是找到刚好背包容量是sum/2装满的时候。
class Solution {
public:bool canPartition(vectorint nums) {int sum 0 , target 0;for(auto it:nums) sum it;//如果和是奇数就不能分成两个相等的子集if(sum%2 1) return false; //目标是找到sum/2target sum/2;vectorvectorint dp(nums.size() , vectorint(target1 , 0));//背包初始化第一行的值第一行是只能放第一个元素//检查背包的大小能否放进去能就放进去第一个元素不能就空着//第一列是背包容量是0的时候dp[i][0]也都是0不用额外初始化for(int j 1 ; jtarget ;j )if(jnums[0]) dp[0][j] nums[0];//开始遍历for(int i1 ; inums.size() ;i){for(int j 1 ; jtarget ;j){//如果当前值大于背包的容量就不放进去if(j nums[i]) dp[i][j] dp[i-1][j];//如果可以放进去就找放进去和不放进去大的一个else dp[i][j] max(dp[i-1][j],dp[i-1][j-nums[i]] nums[i]);}}//最后在背包大小是sum/2的一列里找刚好背包装满的for(int i0; inums.size();i)if(dp[i][target]target) return true;return false;}
};
1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II - 力扣LeetCode
描述
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
示例
示例 1
输入stones [2,7,4,1,8,1] 输出1 解释 组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1] 组合 7 和 8得到 1所以数组转化为 [2,1,1,1] 组合 2 和 1得到 1所以数组转化为 [1,1,1] 组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。
示例 2
输入stones [31,26,33,21,40] 输出5
提示
1 stones.length 30 1 stones[i] 100
代码解析
本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
本题物品的重量为store[i]物品的价值也为store[i]。
动态规划二维数组
找到总重量最接近sum/2 的背包这是一个石头堆。 和另一个堆相减就是剩下的
class Solution {
public:int lastStoneWeightII(vectorint stones) {if(stones.size() 1 ) return stones[0];int sum 0;for(auto it:stones) sum it;vectorvectorint dp (stones.size() , vectorint( sum /2 1 , 0) ) ;for(int j1 ; jsum/2 ;j)if(jstones[0]) dp[0][j] stones[0];//找到背包为sum/2以内最大的种类for(int i1 ;istones.size() ;i){for(int j1 ; jsum/2 ;j){if(jstones[i]) dp[i][j] max( dp[i-1][j] , dp[i-1][j-stones[i]] stones[i]);else dp[i][j] dp[i-1][j];}}//找到最接近sum/2的背包int bag_max 0;for(int i0 ;istones.size() ;i ){if(dp[i][sum/2] bag_max) bag_max dp[i][sum/2];}//计算石头堆的差return (sum - bag_max) - bag_max;}
};
动态规划滚动数组 class Solution {
public:int lastStoneWeightII(vectorint stones) {if(stones.size() 1 ) return stones[0];int sum 0;for(auto it:stones) sum it;vectorint dp (sum /2 1 , 0);for(int i0 ;istones.size() ;i){for(int jsum/2 ; j0 ;j--){if(jstones[i]) dp[j] max( dp[j] , dp[j-stones[i]] stones[i]);else dp[j] dp[j];}}return (sum - dp[sum/2]) - dp[sum/2];}
};
