代码随想录算法训练营day41|动态规划04

最后一块石头的重量||

返回剩余最后一块石头石头最小的可能重量,那么就应该最后剩余的两块石头尽量都等于或接近总重量的一半,这样剩下的就是一半的质量

目标和

给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

回溯的方法

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum == target) {result.push_back(path);}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1);sum -= candidates[i];path.pop_back();}}
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (S > sum) return 0; // 此时没有方案if ((S + sum) % 2) return 0; // 此时没有方案,两个int相加的时候要格外小心数值溢出的问题int bagSize = (S + sum) / 2; // 转变为组合总和问题,bagsize就是要求的和// 以下为回溯法代码result.clear();path.clear();sort(nums.begin(), nums.end()); // 需要排序backtracking(nums, bagSize, 0, 0);return result.size();}
};

解释:假设加法的总和为x,那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target,x = (target + sum) / 2,且若(target+sum)%2!=0的话,x就是无解的

本题要求的,就是装满j的背包有多少种方案,
不放物品i:即背包容量为j,里面不放物品i,装满有dp[i - 1][j]中方法。
放物品i: 即:先空出物品i的容量,背包容量为(j - 物品i容量),放满背包有 dp[i - 1][j - 物品i容量] 种方法

如何初始化
最左上角的元素,如果背包容量为0,就放0种物品,所以就是1种方法,
最左列也应该是为0,但如果存在元素为0的情况,则如下
在这里插入图片描述
二维数组的代码

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=0;for(int i=0;i<nums.size();i++) sum+=nums[i];if(abs(target)>sum) return 0;if((target+sum)%2==1) return 0;int bagSize=(target+sum)/2;vector<vector<int>> dp(nums.size(),vector<int>(bagSize+1,0));if(nums[0]<=bagSize) dp[0][nums[0]]=1;dp[0][0]=1;int numZero=0;for(int i=0;i<nums.size();i++){if(nums[i]==0) numZero++;dp[i][0]=(int) pow(2.0,numZero);//最左列向下递增}for(int i=1;i<nums.size();i++){for(int j=0;j<=bagSize;j++){if(nums[i]>j) dp[i][j]=dp[i-1][j];else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];}}return dp[nums.size()-1][bagSize];}
};

一维的方法初始化起来更简单

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}

总结:在求装满背包有几种方法的情况下,递推公式一般为:dp[j]+=dp[j-nums[i]];

一和零

一道01背包问题,但这个背包有两个维度,一个是m,一个是n

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

注意!!!这里01背包都是从后往前遍历,因为是相当于两个一维动规的叠加

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 oneNum=0,zeroNum=0;for(char c:str){if(c=='0') zeroNum++;else oneNum++;}for(int i=m;i>=zeroNum;i--){//遍历两个背包且从后往前遍历for(int j=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}return dp[m][n];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/17579.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Python+Flask实现随机选谷票游戏

西方曾进行一项著名的投资随机性实验&#xff0c;对比基金经理与猴子在选股上的表现。 实验方法&#xff1a;主持人提供一系列股票&#xff0c;基金经理依靠其专业知识&#xff08;如财务报表、行业趋势、产品市场及公司文化与管理层分析等&#xff09;进行筛选&#xff1b;而…

【Python数据可视化分析实战】数据爬取—京东手机品牌信息数据爬取和数据分析与可视化

大数据分析设计方案 1.数据集来源&#xff1a;https://search.jd.com 2.实现思路&#xff1a; &#xff08;1&#xff09;数据爬取 首先&#xff0c;我们需要从京东平台上采集手机品牌的相关数据。可以通过网络爬虫或API接口等方式获取数据。为了保证数据的完整性和准确性&…

使用 TensorFlow 实现 ZFNet 进行 MNIST 图像分类

ZFNet&#xff08;ZF-Net&#xff09;是由 Matthew Zeiler 和 Rob Fergus 提出的卷积神经网络架构&#xff0c;它在图像分类任务中取得了显著的效果。它在标准卷积神经网络&#xff08;CNN&#xff09;的基础上做了一些创新&#xff0c;例如优化了卷积核大小和池化策略&#xf…

11.15 HTML

传统路线 HTML、CSS、JS AjaxJQueryMySQLJDBCServletJSPEL&JSTLCookieSessionFilterServlet案例MybatisSpringSpringMVCSpringBoot 全新路线 HTM、CSS、JSAjax、AxiosVue、Element前端工程化 vue脚手架MavenSpringBoot基础 基于SpringBoot进行讲解Spring的IOC&#xff…

打造旅游卡服务新标杆:构建SOP框架与智能知识库应用

随着旅游业的蓬勃兴起&#xff0c;旅游卡产品正逐渐成为市场的焦点。为了进一步提升服务质量和客户体验&#xff0c;构建一套高效且标准化的操作流程&#xff08;SOP&#xff09;变得尤为重要。本文将深入探讨如何构建旅游卡的SOP框架&#xff0c;并介绍如何利用智能知识库技术…

Java 简单家居开关系统

1.需求&#xff1a; 面向对象编程实现智能家居控制系统&#xff08;简单的开关&#xff09; 2.实现思路 1.定义设备类&#xff1a;创建设备对象代表家里的设备 JD类&#xff1a; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;D…

Github客户端工具github-desktop使用教程

文章目录 1.客户端工具的介绍2.客户端工具使用感受3.仓库的创建4.初步尝试5.本地文件和仓库路径5.1原理说明5.2修改文件5.3版本号的说明5.4结合码云解释5.5版本号的查找 6.分支管理6.1分支的引入6.2分支合并6.3创建测试仓库6.4创建测试分支6.5合并分支6.6合并效果查看6.7分支冲…

3D Gaussian Splatting的全面理解

1.概述 高斯展开是一种表示 3D 场景和渲染新视图的方法,在“用于实时辐射场渲染的 3D 高斯展开” 中介绍。它可以被认为是类似 NeRF 的模型的替代品,就像过去的 NeRF 一样,高斯飞溅导致了许多新的研究工作,他们选择将其用作各种用例的 3D 世界的底层表示。那么它有什么特别…

Arcgis地图实战三:自定义导航功能的实现

文章目录 1.最终效果预览2.计算两点之间的距离3.将点线画到地图上4.动态展示点线的变化5.动态画线6.动态画点 1.最终效果预览 2.计算两点之间的距离 let dis this.utilsTools.returnDisByCoorTrans(qdXYData, zdXYData, "4549")当距离小于我们在配置文件中预设置的…

【Mysql】Mysql的多表查询---多表联合查询(中)

1、外连接查询 外连接 查询分为左外连接&#xff08;left outer join&#xff09;, 右外连接查询&#xff08;right outer join&#xff09; &#xff0c;满外连接查询&#xff08;full outer join&#xff09;. 注意&#xff1a;oracle 里面有full join &#xf…

Linux:进程状态

文章目录 前言一、初识fork1.1 fork函数的介绍1.2 fork出的子进程存在形式1.3 写时拷贝 二、进程的状态2.1 Linux内核源代码2.2 理解内核链表(重要)2.3 运行状态2.4 阻塞状态2.5 挂起状态 三、Z&#xff08;zombie&#xff09;状态 &#xff0c;僵尸进程四、 孤儿进程总结 前言…

qml显示加载嵌入QWidget窗口

本篇博客介绍如何在qml界面里显示QWidget窗口,开发环境Qt6.5.3 qml. 视频讲解:https://edu.csdn.net/learn/40003/654001?spm=3001.4143 qml和QWidget是两套独立的开发方式,二者的窗口可以相互嵌套显示,本篇博客介绍把QWidget窗口封装为动态库,然后在QML的窗口里显示出来…

【MySQL】多表查询

5. 多表查询 5.1 多表关系 项目开发中&#xff0c;在进行数据库表结构设计时&#xff0c;会根据业务需求及业务模块之间的关系&#xff0c;分析并设计表结构&#xff0c;由于业务之间相互关联&#xff0c;所以各个表结构之间也存在着各种联系&#xff0c;基本上分为三种&#…

2024-11-16 串的存储结构

一、顺序存储。 1.首先定一个静态数组&#xff0c;然后定义i记录串的实际长度。&#xff08;缺点&#xff1a;长度不可变&#xff09; 2.使用malloc申请动态空间&#xff0c;定义指针指向串的地址。&#xff08;需手动ferr&#xff09; 方案一&#xff1a; 数组末尾记录长度 …

nodejs21: 快速构建自定义设计样式Tailwind CSS

Tailwind CSS 是一个功能强大的低级 CSS 框架&#xff0c;只需书写 HTML 代码&#xff0c;无需书写 CSS&#xff0c;即可快速构建美观的网站。 1. 安装 Tailwind CSS React 项目中安装 Tailwind CSS&#xff1a; 1.1 安装 Tailwind CSS 和相关依赖 安装 Tailwind CSS: npm…

Windows 安装Docker For Desktop概要

Windows 安装docker 下载部分的工作需要使用科学技术。如果没有可以联系博主发送已下载好的文件。 本文档不涉及技术的讲解&#xff0c;仅有安装的步骤。 准备工作 包含下载与环境准备&#xff0c;下载的文件仅下载&#xff0c;在后续步骤进行安装。 微软关于wsl的文档&…

对称加密算法DES的实现

一、实验目的 1、了解对称密码体制基本原理 2、掌握编程语言实现对称加密、解密 二、实验原理 DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位&#xff0c;产生最大 64 位的分组大小。这是一个迭代的分组密码&#xff0c;使用称为 Feistel 的技术&#xff0c;其中将加密…

三十八、Python(pytest框架-上)

一、介绍 框架&#xff08;framework&#xff09;&#xff1a;框架是为解决一类事情的功能集合。 pytest框架&#xff1a;pytest框架是单元测试框架&#xff0c;这是第三方框架想要使用必须要安装&#xff0c;可以使用pytest来作为自动化测试执行框架&#xff0c;用来管理测试…

《Django 5 By Example》阅读笔记:p165-p210

《Django 5 By Example》学习第6天&#xff0c;p165-p210总结&#xff0c;总计46页。 一、技术总结 1.bookmarks项目 (1)登录认证 作者这里使用的是Django自带的auth。 (2)上传头像 图片处理&#xff0c;使用Pillow。 (3)扩展user 扩展user模型与自带的user使用外键进行…

shell基础(3)

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团…