电商网站首页大港做网站

当前位置： 首页 > news >正文

电商网站首页,大港做网站,唐山快速建站公司,如何优化网站首页DP刷题练习#xff08;二#xff09; 文章内容学习自代码随想录#xff0c;感谢carl#xff01;#xff01;#xff01;#xff01; 文章目录 DP刷题练习#xff08;二#xff09;[1049. 最后一块石头的重量 II - 力扣#xff08;LeetCode#xff09;](https://le…DP刷题练习二 文章内容学习自代码随想录感谢carl 文章目录 DP刷题练习二1049. 最后一块石头的重量 II - 力扣LeetCode这个背包最多能装多少494. 目标和 - 力扣LeetCode装满这个背包有多少种方法474. 一和零 - 力扣LeetCode装满这个背包最多要用多少物品518. 零钱兑换 II - 力扣LeetCode完全背包装满有多少种方法377. 组合总和 Ⅳ - 力扣LeetCode322. 零钱兑换 - 力扣LeetCode完全背包装满要最少需要多少种物品279. 完全平方数 - 力扣LeetCode139. 单词拆分 - 力扣LeetCode 1049. 最后一块石头的重量 II - 力扣LeetCode这个背包最多能装多少 石头相撞我们想要最后得到一块最小质量的石头甚至没有我们就要尽可能的把他分成两堆那就是0/1背包 我们有一个一半总质量的背包尽可能装满他然后最后拿这两堆相撞返回剩下的值 这次我写的是一维数组版本 int lastStoneWeightII(vectorint stones) {int mstones.size();//石头块数int sum0;for(int i0;im;i) sumstones[i];int nsum/2;//尽可能分成相同的两堆int dp[n1];//dp[j]表示容量为j的背包所能装下的最大重量for(int j0;jn;j){//初始化if(jstones[0]) dp[j]stones[0];else dp[j]0;}for(int i1;im;i){//先物品for(int jn;jstones[i];j–){//后背包dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}int x(sum-dp[n])-dp[n];return x;}494. 目标和 - 力扣LeetCode装满这个背包有多少种方法 样例[1,1,1,1,1] /*我们要使nums数组中的一部分为正一部分为负然后让他们的和等于target这是我们的目标 我们将正数的这一部分记作left[]负数这一部分记作right[] 于是我们有: leftrightsum rightsum-left left-righttarget 所以left-(sum-left)target left(targetsum)/2这个数是非负数的和如果是负数的话不符合条件直接return 0就好因为这里的都是非负整数集合所以算出的targetsum%2如果不能整除的话那就永远的凑不出target 直接return 0 */所以本题就演变成给你一个容量为left的背包问你装满这个背包总共有多少种方案依然是0/1背包问题 int findTargetSumWays(vectorint nums, int target) {int sum0;for(int i0;inums.size();i) sumnums[i];//(sumtaget)/2是号元素之和必须是非负数if((sumtarget)%2!0||(sumtarget)/20) return 0;int bag_size(sumtarget)/2;int dp[bag_size10];//dp[j]表示用数组中若干个元素组成的和为j的方案数memset(dp,0,sizeof(dp));dp[0]1;for(int i0;inums.size();i){for(int jbag_size;jnums[i];j–){dp[j]dp[j]dp[j-nums[i]];//原来装满的方案加上上这个数才装满的方案}}return dp[bag_size];}所以我们可以把状态定义为 dp [ j ]表示用数组中若干个元素组成和为j的方案数。那么状态转移方程就是 dp[j] dp[j] dp[j - nums[i]];这个方程的意思是如果我们要用若干个元素组成和为j的方案数那么有两种选择不选第i个元素或者选第i个元素。如果不选第i个元素那么原来已经有多少种方案数就不变如果选第i个元素那么剩下要组成和为j - nums[i], 的方案数就等于dp[j - nums[i]]。所以两种选择相加就是dp【j】。 但是在实现这个状态转移方程时有一个细节需要注意由于每次更新dp【j】都依赖于之前计算过得dp值也就是说当前行依赖于上一行所以我们必须从后往前遍历更新dp值也就是说从右往左更新否则会覆盖掉之前需要用到得值。 最后返回dp【bag_size】即可。

1. 一和零 - 力扣LeetCode装满这个背包最多要用多少物品 本题让我们找出一个满足m个0n个1的最大子集 我们将问题抽象为一个背包将问题转化为当背包可以装m个0n个1时装满这个背包最多能用多少种物品 dp[i][j]//背包能装i个0j个1时最多要用dp[i][j]个物品//设这个物品有x个0y个1那么递推式就可以为 dp[i][j]max(dp[i-x][j-y]1,dp[i][j]);int findMaxForm(vectorstring strs, int m, int n) {int dp[110][110];//dp[i][j]表示当背包能装i个0j个1的时候最多能装dp[i][j]个物品memset(dp,0,sizeof(dp));for(string str:strs){int x0,y0;for(char c:str){if(c0) x;else y;}for(int im;ix;i–){for(int jn;jy;j–){dp[i][j]max(dp[i-x][j-y]1,dp[i][j]);}}}return dp[m][n];}总结以上几道题全都是0/1背包问题0/1背包问题的特征是物品只能用一次 由此演变出的四类问题这个背包能不能装满这个背包最多能装多少装满这个背包有多少种方案装满这个背包最多要用多少种物品 需要我们勤加练习接下来是完全背包问题
2. 零钱兑换 II - 力扣LeetCode完全背包装满有多少种方法 本题求得还是一种组合数顺序是无关的注意本题只能先遍历物品后遍历背包因为只有先遍历物品后遍历背包你得出来的才是组合数否则你得出来的就是排列数而排列数是考究顺序的 int change(int amount, vectorint coins) {int dp[amount10];//dp[j]表示用coins中任意硬币能组成j的最大方案数为dp[j]memset(dp,0,sizeof(dp));dp[0]1;//组合成0块钱有一种方案for(int i0;icoins.size();i)//先物品再容量for(int jcoins[i];jamount;j){//完全背包是从前往后遍历为什么因为物品可以无限用所以你当前的状态dp[j]dp[j]dp[j-coins[i]]; //是由你已经往里放了这个东西转移而来的意味你可以再放一次}return dp[amount];}组合数先遍历物品后遍历背包是这样比如外层循环固定coins【1】在内层循环遍历背包时随着背包不断增加coins【1】可以重复被添加进来而由于外层循环固定了因此coins【2】只能在下一次外层循环添加进不同大小的背包中这么看的话coins【i1】只能在coins【i】之后了只有1234的情况 排列数如果先遍历背包后遍历物品那么外层循环先固定背包大小j然后在大小为j的背包中循环遍历添加物品然后在下次外层循环背包大小变为j1此时仍要执行内层循环遍历添加物品也就会出现在上一轮外层循环中添加coins【2】的基础上还能再添加coins【1】的情况那么就有了coins【1】在coins【2】之后的情况了。会出现12 21的情况
3. 组合总和 Ⅳ - 力扣LeetCode 像这道题他遍历的就是排列数因为他将12 |21区分为两个不同的组合所以应该先遍历容量再遍历数量 int combinationSum4(vectorint nums, int target) {unsigned long long dp[1010];memset(dp,0,sizeof(dp));dp[0]1;for(int j1;jtarget;j)//先遍历容量for(int i0;inums.size();i){//再遍历物品求的是排列数if(jnums[i]) dp[j]dp[j]dp[j-nums[i]];}return dp[target];}322. 零钱兑换 - 力扣LeetCode完全背包装满要最少需要多少种物品 这道题是求物品可以无限放装满背包最少需要多少枚硬币 int coinChange(vectorint coins, int amount) {int dp[amount10];//dp[j]表示装满容量为j的背包最少需要dp[j]个物品memset(dp,0x3f,sizeof(dp)); //此处初始化为最大值是服务于mindp[0]0; //初始化成0是题目说输入coins [1], amount 0 输出0for(int i0;icoins.size();i){for(int j1;jamount;j){if(jcoins[i]) dp[j]min(dp[j],dp[j-coins[i]]1);}}if (dp[amount]0x3f3f3f) return -1;else return dp[amount];}279. 完全平方数 - 力扣LeetCode 我们看数据大小先确定完全平方数超不过100*100自己拼凑一个序列然后秒了 int numSquares(int n) {int nums[110];for(int i1;i100;i) nums[i]i*i;int dp[n1];//dp[j]表示装满容量为j的背包使用的最小完全平方数的数量为dp[j]memset(dp,0x3f,sizeof(dp));dp[0]0;for(int i1;i100;i){for(int j1;jn;j){if(jnums[i]) dp[j]min(dp[j],dp[j-nums[i]]1);}}return dp[n];}139. 单词拆分 - 力扣LeetCode 如果dp【j】就是dp【i】前面的字段可以被拼接并且 i-j到i这段也可以被word表达那么整个长度为i的字段就是可以被拼接的直接跳出不能再做更新 bool wordBreak(string s, vectorstring wordDict) {setstring word;for(string w:wordDict){word.insert(w);}vectorint dp(s.size()1,false);//dp[i]表示长度为i的字符串能否被字典中的单词组成为dp[i]dp[0]true;for(int i1;is.size();i){ //串的长度,这里我们必须先遍历背包因为我们处理的是排列物品顺序是有影响的for(int j0;ji;j){ //串前面的长度if(dp[j]word.find(s.substr(j,i-j))!word.end()) {dp[i]true;break;//可以拼接就可以跳出了}}}return dp[s.size()];}