力扣● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

news/2024/5/25 2:57:23

● 1049. 最后一块石头的重量 II

题目要把石头分成两堆,这两堆的重量差值最小。相撞之后剩下的石头重量就最小。其实就是要尽量把石头分为差不多重量的两堆,和昨天的● 416. 分割等和子集相似,这样就转换成了01背包问题。

和416题一样,背包里面放的是两堆其中一堆的石头,需要尽量装满sum/2,其中一堆越接近sum/2,两堆石头重量就越差不多。所以这里价值和重量是等同的 ,weight数组就是stones数组,value数组也是stones数组。容量begweight就得取sum/2。

代码如下,注意最后返回的是另一堆的重量减去背包里的重量,因为背包重量≤sum/2,所以另一堆重量≥背包重量。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum=0;for(int a:stones)sum+=a;//求和int begweight=sum/2;//背包容量vector<int> dp(begweight+1,0);  //已初始化for(int i=0;i<stones.size();++i){for(int j=begweight;j>=stones[i];--j){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]); //weight和value数组都是stones}}return (sum-2*dp[begweight]);   //dp[begweight]是背包里的重量}
};

● 494. 目标和

在每个数前面要么添加"+",要么添加"-",所以也是分为两堆:设为left和right。添加"+"的是left,添加"-"的是right。

有:left-right=target;left+right=sum。

所以left=(sum+target)/2。其中sum和target都已知,所以left可知,问题就是在集合nums中统计和为left的组合数量。所以背包容量应该为left的值。

有两个情况可以直接返回:如果sum+target的和是奇数,那left是不存在的,返回0;如果target的绝对值比sum还大,怎么添加"+"和"-"都不会得到left,也返回0.

动归五部曲:

1. DP数组及其下标的含义。dp[j]:装满容量为j的包,有dp[j]种方法。

所以和昨天的不同,这个是装满容量为j,所以背包容量直接就是j,昨天的是最大容量为j。而且这个是组合问题。所以五部曲得重新思考。


2. 递推公式。dp[j]背包现在容量是j,考虑最后放入的物品,有可能是小于等于j的物品中的任意一个,那么对于所有的nums[i]≤j,都可能是最后一步放入的。所以放一个其中的nums[i],对应的方法数应该是dp[j-nums[i]]。所以统计dp[j]就得考虑所有的小于j的nums[i]在背包里面的情况,那么就需要把所有的dp[j-nums[i]]加起来,才是dp[j]的值。例子如下:

dp[j],j 为5。如果小于j的nums[i]有1,2,3,4,5,那么5种情况,都考虑,然后一起加上。
  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包。
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包。
  • 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包。

所以dp[j]= \sum_{nums[i]\leq j}^{}dp[j-nums[i]]

这个公式在后面背包解决排列组合问题的时候还会用到。

3. DP数组如何初始化。dp[0] 需要= 1,虽然=1不好解释,但是如果初始化为0的话,之后怎么加结果都只会是0,所以肯定是不行的。

4. 遍历顺序。昨天滚动一维数组中说过的,先物品再背包,而且背包要倒序。


5. 打印DP数组。动手模拟,输出检查。

输入:nums: [1, 1, 1, 1, 1], S: 3

bagweight = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:

代码:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(int a:nums)sum+=a;//2种没有结果的情况if(abs(target)>sum)return 0;if((sum+target)%2==1)return 0;//背包容量begweight=left=(sum+target)/2int begweight=(sum+target)/2;vector<int> dp(begweight+1,0);//不能是0.dp[0]=1;for(int i=0;i<nums.size();++i){for(int j=begweight;j>=nums[i];--j){dp[j]+=dp[j-nums[i]];}}return dp[begweight];}
};

● 474.一和零

输入有m和n,输出包含m个0和n个1的子集的最大长度。那么dp数组应该有两个维度,最后应该返回dp[m][n]。

动规五部曲:

1. DP数组及其下标的含义。

dp[i][j]:背包里面有 i 个0和 j 个1,可以最多装下dp[i][j]个物品(集合)。


2. 递推公式。

每个物品的重量/价值也应该是两个维度:x个0和y个1。所以有value0和value1两个数组,统计出每个物品两个维度的价值。这个题和前几个一样,价值 和重量一样,所以下面统称重量。

回想之前一维滚动数组的递推公式:dp[ j ]=max(dp[ j ], dp[ j - weight[ i ]] +value[ i ]);可见这个公式的重要性,所以还是根据这种思想,对于每个物品(每个k),都考虑没放进来之前的背包重量,是dp[ i- x ] [ j - y ],放不进去的话就取上一轮的dp[i][j]。所以递推公式仍然是取这两种情况的最大值:

dp[ i ][ j ]=max( dp[ i ][ j ], dp[ i- x ] [ j - y ] + 1)。

注意这个是一维滚动数组的变形,但是因为dp数组扩展成二维,所以之前一维滚动数组的循环j这y一层循环应该变成两层循环i和j,加上最外层循环应该有3层for循环。


3. DP数组如何初始化。显然dp[0][0]是0,其他的值为了不会出现递推公式里面取max取到自己随便设置的一个正数,也应该都初始为0。


4. 遍历顺序。同样是先物品再背包,且背包有二维,i和j都应该倒序遍历,而且条件要使得递推公式的下标有效。


5. 打印DP数组。

以输入:["10","0001","111001","1","0"],m = 3,n = 3为例

代码如下:

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));    for(string str:strs){int x=0,y=0;//统计x和yfor(char s:str){if(s=='0')  x++;else y++;}//二维递推for(int i=m;i>=x;--i){for(int j=n;j>=y;--j){dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);}}}return dp[m][n];}
};


http://www.mrgr.cn/p/87638271

相关文章

【C++从0到王者】第四十六站:图的深度优先与广度优先

文章目录 一、图的遍历二、广度优先遍历1.思想2.算法实现3.六度好友 三、深度优先遍历1.思想2.代码实现 四、其他问题 一、图的遍历 对于图而言&#xff0c;我们的遍历一般是遍历顶点&#xff0c;而不是边&#xff0c;因为边的遍历是比较简单的&#xff0c;就是邻接矩阵或者邻接…

从 iOS 设备恢复数据的 20 个iOS 数据恢复工具

作为 iPhone、iPad 或 iPod 用户&#xff0c;您可能普遍担心自己可能会丢失存储在珍贵 iOS 设备中的所有宝贵数据。数据丢失的原因多种多样&#xff0c;这里列出了一些常见原因&#xff1a; 1. iOS 软件更新 2. 恢复出厂设置 3. 越狱 4. 误操作删除数据 5. iOS 设备崩溃 …

使用openai-whisper实现语音转文字

使用openai-whisper实现语音转文字 1 安装依赖 1.1 Windows下安装ffmpeg FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的完整解决方案。 # ffmpeg官网 https://ffm…

WhatsApp代理設置指南

某些情況下&#xff0c;你可能需要使用WhatsApp代理來確保WhatsApp順暢且不受限制的通信。本篇文章將講解WhatsApp代理是什麼、WhatsApp代理的使用場景、以及如何在WhatsApp中使用和設置代理。​​​​​​​ WhatsApp代理指什麼? WhatsApp代理是位於可以訪問WhatsApp的國家或…

多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测

多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网…

《汇编语言》- 读书笔记 - 第13章-int 指令

《汇编语言》- 读书笔记 - 第13章-int 指令 13.1 int 指令13.2 编写供应用程序调用的中断例程中断例程&#xff1a;求一 word 型数据的平方主程序中断处理程序执行效果 中断例程&#xff1a;将一个全是字母&#xff0c;以0结尾的字符串&#xff0c;转化为大写主程序中断处理程序…

【C++】C++的四种强制类型转换

1、C语言中的类型转换 在C语言中&#xff0c;如果赋值运算符左右两侧类型不同&#xff0c;或者形参与实参类型不匹配&#xff0c;或者返回值类型与接收返回值类型不一致时&#xff0c;就需要发生类型转化&#xff0c;C语言中总共有两种形式的类型转换&#xff1a;隐式类型转换…

mysql,for循环执行sql

遇到一个问题&#xff0c;我需要模拟上百万数据来优化sql&#xff0c;线上数据down不下来&#xff0c;测试库又没有&#xff0c;写代码执行要么慢要么就是sql语句太长。 于是&#xff0c;直接用mysql自带的功能去实现&#xff01; 简单而简单 mysql可以for循环&#xff1f;没…

Docker技术概论(4):Docker CLI 基本用法解析

Docker技术概论&#xff08;4&#xff09; Docker CLI 基本用法解析 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:http…

Spring AI上架

Spring AI 来了 Spring AI 是 AI 工程师的一个应用框架,它提供了一个友好的 API 和开发 AI 应用的抽象,旨在简化 AI 应用的开发工序。 提供对常见模型的接入能力,目前已经上架 https://start.spring.io/,提供大家测试访问。(请注意虽然已经上架 start.spring.io,但目前还…

文件基础和文件fd

文章目录 预备知识C语言的文件接口系统调用文件fd 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。 点击跳转到网站。 预备知识 我们平时说文件就是说文件里…

cyi青少年CTF擂台挑战赛 2024 #Round 1 wp

cyi青少年CTF擂台挑战赛 2024 #Round 1 wpWEB EasyMD5 靶机真不敢恭维 一个文件上传界面,得上传pdf传两个pdfhttps://www.cnblogs.com/wysngblogs/p/15905398.html 这篇文章看到md5碰撞,找到个工具fastcoll_v1.0.0.5 https://www.win.tue.nl/hashclash/后续写的wp,flag可能…

Gitlab Runner自动推送Docker映像

接上文,增加两个stage 最简单的推送,其实是在docker build后边带上--push的开关即可。 但是不经过测试就上传,Docker仓库里很快会堆满垃圾。 所以我们设计新增两个场景,经过测试之后才push映像去仓库。 stages:- build-docker-image- test- push-image variables:PAY_IMAGE…

黑马JavaWeb课程中安装vue脚手架出现的问题

1 安装node.js 要想前端工程化&#xff0c;必须安装node.js&#xff0c;前端工程化的环境。 在成功安装node.js后&#xff0c; 修改全局包安装路径为Node.js安装目录&#xff0c; 修改npm镜像源为淘宝镜像源&#xff0c;这里出现第一个问题&#xff0c;视频中给的淘宝镜像为&…

python实现常见一元随机变量的概率分布

一. 随机变量 随机变量是一个从样本空间 Ω \Omega Ω到实数空间 R R R的函数&#xff0c;比如随机变量 X X X可以表示投骰子的点数。随机变量一般可以分为两类&#xff1a; 离散型随机变量&#xff1a;随机变量的取值为有限个。连续型随机变量&#xff1a;随机变量的取值是连…

关于Windows 10的兼容模式,看这篇文章就够了

这篇文章解释了如何使用Windows兼容模式在Windows 10上完美地运行旧版本的Windows程序。 如何更改Windows 10兼容模式设置 如果疑难解答没有完成任务&#xff0c;并且你知道该程序以前使用过哪个版本的Windows&#xff0c;则可以手动更改Windows 10兼容模式的设置&#xff1a…

Spring-自动配置

自动配置流程细节梳理: 1、导入starter-web:导入了web开发场景1、场景启动器导入了相关场景的所有依赖:starter-json、starter-tomcat、springmvc 2、每个场景启动器都引入了一个spring-boot-starter,核心场景启动器。(上面三个也有) 3、核心场景启动器引入了spring-boot-a…

[回归指标]R2、PCC(Pearson’s r )

R2相关系数 R2相关系数很熟悉了&#xff0c;就不具体解释了。 皮尔逊相关系数&#xff08;PCC&#xff09; 皮尔逊相关系数是研究变量之间线性相关程度的量&#xff0c;R方和PCC是不同的指标。R方衡量x和y的接近程度&#xff0c;PCC衡量的是x和y的变化趋势是否相同。R方是不…

《TCP/IP详解 卷一》第9章 广播和组播

目录 9.1 引言 9.2 广播 9.2.1 使用广播地址 9.2.2 发送广播数据报 9.3 组播 9.3.1 将组播IP地址转换为组播MAC地址 9.3.2 例子 9.3.3 发送组播数据报 9.3.4 接收组播数据报 9.3.5 主机地址过滤 9.4 IGMP协议和MLD协议 9.4.1 组成员的IGMP和MLD处理 9.4.2 组播路由…

Gitlab Runner自动制作C#网站项目的Docker映像

概述 代码签入Gitlab后,Gitlab Runner自动执行docker build,构建网站应用的Docker映像。 在Visual Studio 2022中创建解决方案在Gitlab中创建项目 这一步省略。 签入源代码到Gitlab为项目添加Dockerfile在解决方案根目录下创建“.gitlab-ci.yml” stages:- build-docker-imag…