建设部网站令第77号,WordPress页面构建器,想做网站的公司,品牌网站设计公司哪家好题目1#xff1a;1049 最后一块石头的重量
题目链接#xff1a;最后一块石头的重量
对题目的理解
整数数组stone[i]表示第i块石头的重量#xff0c;每次从中选出任意两块石头(xy)粉碎
如果两块石头重量相等#xff0c;就会被完全粉碎#xff1b;如果不等#xff…题目11049 最后一块石头的重量
题目链接最后一块石头的重量
对题目的理解
整数数组stone[i]表示第i块石头的重量每次从中选出任意两块石头(xy)粉碎
如果两块石头重量相等就会被完全粉碎如果不等那么重量轻(x)的石头会被粉碎另一块石头重量变为y-x
每次最多剩下一块石头返回此石头可能的最小重量如果没有石头剩下就返回0
stone数组中的元素在1~100之间数组长度在1~30之间
每次让数值相近的石头一起粉碎这样最终得到的重量会减少本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
本题物品的重量是stones[i],物品的价值也是stones[i]
动规五部曲
1dp数组的含义及下标i的含义
dp[j]:表示背包容量为j背的最大价值
本题表示背包中容量是j时最大重量是dp[j]
2递推公式
01背包dp[j]max(dp[j],dp[j-weight[i]]value[i])
dp[j]max(dp[j],dp[j-stones[i]]stones[i])
3dp数组初始化
dp[0]0 ,根据递推公式非零下标对应的dp[j]也初始化为0这样才不会覆盖初始值
1 stones.length 301 stones[i] 100所以最大重量就是30 * 100 但是背包只需要装最大重量的一半即可因为将石头分成重量相等的两堆targetsum/23000/21500
4遍历顺序
先正序遍历物品后倒序遍历背包
for(i0;istones.size();i){ for(jtarget;jstones[i];j--)}
5打印dp数组
最后dp[target]里是容量为target的背包所能背的最大重量那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]
因为targetsum/2,是直接抹去小数部分所以sum-dp[target]target
最终石头的最小重量是result(sum-dp[target])-dp[target]
代码
class Solution {
public:int lastStoneWeightII(vectorint stones) {//数组长度最大是30数组中的元素最大是100所以dp数组承受的最大重量是30*1003000分成重量相同的两堆所以大小是15001//dp数组初始化vectorint dp(1501,0);int sum 0;for(int i0;istones.size();i){sum stones[i];}int target sum/2;//递推,先正序遍历物品后倒序遍历背包for(int i0;istones.size();i){for(int jtarget;jstones[i];j--){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}int result sum-dp[target]-dp[target];return result;}
};
时间复杂度O(m × n) , m是石头总重量准确的说是总重量的一半n为石头块数空间复杂度O(m)
题目2494 目标和
题目链接目标和
对题目的理解
非负整数数组的每个数字前添加 或 - 得到表达式计算表达式运算结果等于target的不同表达式的数目
本题还是分成两个部分加法集合left 减法集合right这两个集合满足下面的两个等式①②
① leftrightsum
② left-righttarget
rightsum-left
left-(sum-left)target--2left-sumtaget left(targetsum)/2 注只有能整除才能找到
如果不能整除则不存在这样的元素组合使得运算结果等于target
如果target的绝对值的大于sum也是无解的
背包容量是left时,看元素中有多少种方式能够装满这个背包,每个元素只用1次是01背包问题
动规五部曲
1dp[j]数组即下标j的含义
背包容量为j时装满背包有dp[j]种方法
2递推公式 递推公式dp[j] dp[j-nums[i]] 在后面在讲解背包解决排列组合问题的时候还会用到
3dp数组初始化
dp[0]1,如果数组[0] target 0那么 left (target sum) / 2 0, dp[0]也应该是1 也就是说给数组里的元素 0 前面无论放加法还是减法都是 1 种方法。
根据递推公式 因为递推公式是累加的dp[j]要保证是0的初始值才能正确的由dp[j - nums[i]]推导出来。,所以非零下标的dp[j]初始为0
4遍历顺序
01背包正序遍历物品(元素)倒序遍历背包left
5打印dp数组 代码
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum0;for(int i0;inums.size();i){sum nums[i];}int left (targetsum)/2;//dp数组里面尽可能地装left容量 -500~1000if((targetsum)%21) return 0;if(abs(target)sum) return 0;//初始化dp数组vectorint dp(left1,0);dp[0]1;//递推for(int i0;inums.size();i){for(int jleft;jnums[i];j--){dp[j] dp[j-nums[i]];}}return dp[left];}
};
时间复杂度O(n × m)n为正数个数m为背包容量空间复杂度O(m)m为背包容量
本题记住求装满背包有几种方法递推公式为
dp[j] dp[j-nums[i]];
题目3474一和零
题目链接一和零
对题目的理解
返回二进制字符串数组strs最大子集长度该子集中最多有m个0和n个1二进制字符串仅由01组成
题目要求strs字符串数组中至少有1个字符串最多有600个字符串每个字符串的长度至少为1最多是100
背包有两个维度m个0和n个1装满这个背包有多少个物品
不同长度的字符串就是不同大小的待装物品每个物品只能使用1次所以是01背包问题
动规五部曲
1dp数组及下标i的含义
二维dp数组dp[i][j] 装满i个0j个1的背包最多背了dp[i][j]个物品
2递推公式
01背包递推公式dp[j]max(dp[j],dp[j-weight[i]]value[i])
每个物品的重量是x个0y个1,是两个维度所以递推公式为dp[i][j]max(dp[i][j], dp[i-x][j-y]1)
3dp数组初始化
dp[0][0]0 非零下标 若初始化为一个较大的正整数那么根据递推公式值会被覆盖掉
所以非零下标的dp[j]也初始化为非负整数的最小值即0
4遍历顺序
01背包先正序遍历物品strs里的字符串后倒序遍历背包两个维度m和n
5打印dp数组
代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {//定义并初始化dp数组这个数组是一个二维数组,有这两个重量0和1vectorvectorint dp(m1,vectorint(n1,0));//递推,先正序遍历物品后倒序遍历背包for(string str:strs){//遍历物品字符串数组int x0;//记录当前字符串中0的个数int y0;//记录当前字符串中1的个数for(char c:str){//遍历字符串中的每个字符,统计字符串中0和1的数量if(c0) x;else y;} for(int im;ix;i--){//遍历背包for(int jn;jy;j--){dp[i][j]max(dp[i][j],dp[i-x][j-y]1);}}}return dp[m][n];}
};
时间复杂度: O(kmn)k 为strs的长度空间复杂度: O(mn)
