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

每日一题 494目标和(0-1背包)(灵神笔记)

0-1背包模版

有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?
当前操作?枚举第i个物品选还是不选,不选容量不变,选容量减少
子问题?从前i个物品中的最大容量和
下一个子问题?不选:剩余容量为c,前i-1个物品中的最大容量和;选:
剩余容量为c-w[i],前i个物品中的最大容量和

public int dfs(int i, int c) {if (i < 0) {return 0;}if (c < w[i]) {return dfs(i - 1, c);}return dfs(n - 1, capacity);}

题目

目标和
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2:

输入:nums = [1], target = 1
输出:1

提示:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

题解

记忆化搜索

class Solution {private int[] nums;private int[][] cache;public int findTargetSumWays(int[] nums, int target) {// p 正数的和// s nums的和// target = p - (s - p)// p = (s + t)/2//题目转化为从nums选择数使他们恰好等于(s + t)/2// 其中(s+t)必须为偶数for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;this.nums = nums;int n = nums.length;cache = new int[n][target + 1];for (int i = 0; i < n ; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1,target);}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 1 : 0;}if (cache[i][c] != -1) {return cache[i][c];}if (c < nums[i]) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);}
}

递推

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[n+1][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[i+1][c] = f[i][c];} else {f[i+1][c] = f[i][c] + f[i][c-nums[i]];}}}return f[n][target];}
}

空间优化(两个数组)

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[2][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[(i+1)%2][c] = f[i%2][c];} else {f[(i+1)%2][c] = f[i%2][c] + f[i%2][c-nums[i]];}}}return f[n%2][target];}
}

空间优化(一个数组)

class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[] f = new int[target+1];f[0] = 1;for (int x : nums) {for (int c = target; c >= x; c--) {f[c] += f[c-x];}}return f[target];}
}

相关文章:

每日一题 494目标和(0-1背包)(灵神笔记)

0-1背包模版 有n个物品&#xff0c;它们有各自的体积和价值&#xff0c;现有给定容量的背包&#xff0c;如何让背包里装入的物品具有最大的价值总和&#xff1f; 当前操作&#xff1f;枚举第i个物品选还是不选&#xff0c;不选容量不变&#xff0c;选容量减少 子问题&#xff…...

软件测试工作步骤详情

软件测试步骤按照研发阶段一般分为5个部分&#xff1a;单元测试、集成测试、确认测试、系统测试、验收测试&#xff0c;下面将不同阶段需要的一些工作内容做一下梳理希望可以帮助到大家。 一、单元测试的内容&#xff1a;&#xff08;白盒为主&#xff0c;黑盒为辅&#xff09;…...

java项目之列车票务信息管理系统(ssm源码+文档)

项目简介 列车票务信息管理系统实现了以下功能&#xff1a; 管理员&#xff1a;个人中心、用户管理、车票信息管理、购票指南管理、管理员管理、论坛管理、我的收藏管理、系统管理、订单管理。前台首页&#xff1a;首页、车票信息、购票指南、我的收藏管理、论坛信息、我的、…...

【Pytorch笔记】3.数学运算

深度之眼官方账号 - 01-03-mp4-张量操作与线性回归 torch.add() 功能&#xff1a;逐元素计算inputalphaother。 torch.add(input,alpha1,other,outNone)input&#xff1a;tensor&#xff1b; alpha&#xff1a;other的系数&#xff0c;是个实数&#xff1b; other&#xff1…...

MeterSphere 监控方案

前言&#xff1a;在部署MeterSphere之后&#xff0c;很多时候需要看下MeterSphere服务的监控信息&#xff0c;虽然有监控告警脚本&#xff0c;但还不是太直观&#xff0c;所以就结合 PrometheusExporterGrafana 部署一套完整的MeterSphere监控方案。 首先我们先罗列一下需要监控…...

elementui-plus+ts+axios使用el-upload组件自定义上传

1.前言&#xff1a; 使用element ui有很多便捷之处&#xff0c;但是由于是封装的组件和自己写还是有些许的不一样&#xff0c;这里主要解决几个问题。 1. 如何获取子组件实例 2. 如何自定义上传方法 2.两个问题&#xff1a; ⛺️ 获取子组件实例 实际上vue一般通过ref获取子组…...

【STM32单片机】u8g2智能风扇设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器&#xff0c;使用按键、IIC OLED模块、DS18B20温度传感器、直流电机、红外遥控等。 主要功能&#xff1a; 初始化后进入温度显示界面&#xff0c;系统初始状态为手动…...

Java中的IO流的缓冲流

不爱生姜不吃醋⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始&#xff0c;不如现在行动&#xff01; 文章目录 &#x1f334;IO流体系结构&#x1f334;缓冲流1.提高效率的原理2.缓冲流的类型3.字符缓冲流两个特有方法 &#x1f334;总结 &#x1f334;IO流体系…...

7、SpringBoot_高级配置

一、配置高级 1.临时属性设置 1.1引出问题 如果目标电脑上8080端口已经使用&#xff0c;再次使用该端口会出现端口占用问题 解决方式 重新更换配置文件修改端口打包通过临时属性配置新端口更换配置文件 1.2添加临时属性配置 通过临时属性修改8080端口 java -jar 项目.jar…...

cocos2dx查看版本号的方法

打开文件&#xff1a;项目根目录\frameworks\cocos2d-x\docs\RELEASE_NOTES.md 知道引擎版本号的意义&#xff1a; 1.面试中经常被问到(面试官想知道你会不会查版本号&#xff0c;你会查也不一定会去看&#xff0c;如果你去看了说明你是一个有心人&#xff0c;或者想深入研究下…...

某高校的毕设

最近通过某个平台接的单子&#xff0c;最后Kali做的测试没有公开可以私聊给教程。 下面是规划与配置 1.vlan方面&#xff1a;推荐一个vlan下的所有主机为一个子网网段 连接电脑和http客户端的接口配置为access接口 交换机与交换机或路由器连接的接口配置为trunk接口---也可以…...

利用uvicorn、Starlette和pipeline将一个训练好的大模型发布成一个web服务

技术名词&#xff1a; 1、Starlette&#xff1a; 它是一个轻量级、高度可用性和可扩展性的Web框架&#xff0c;它专门为异步应用程序设计。 Starlette基于Python 3.6的异步/协程语法&#xff0c;具有快速响应性能和低延迟。你可以将它理解为Java的Spring。 安装&#xff1a;…...

贝赛尔曲线 - Vue3实现加入购物车抛物线效果组件

贝赛尔曲线 - Vue3实现加入购物车抛物线效果组件&#xff08;可连续多个动画&#xff0c;动态回收DOM&#xff09; 前言 在前几天的一次迭代中&#xff0c;我遇到了这么一个需求&#xff0c;模仿支付宝首页应用中心的编辑功能&#xff0c;支持编辑首页展示的应用&#xff0c;…...

AddressSanitizer failed to allocate 0xdfff0001000 (15392894357504) bytes解决方法

打开一个编译选项启用ASan的程序&#xff1a; AddressSanitizer failed to allocate 0xdfff0001000 (15392894357504) bytes然后程序启动失败。 原因&#xff1a; [cfe-dev] Question about Clang/LLVM addresssanitizer /proc/sys/vm/overcommit_memory是一个用于控制内存…...

Fortinet 2023上半年全球威胁态势研究报告:勒索软件检测成下降趋势,针对性攻击持续升温

近日&#xff0c;专注于推动网络与安全融合的全球网络安全领导者Fortinet&#xff08;NASDAQ&#xff1a;FTNT&#xff09;&#xff0c;发布《2023上半年全球威胁态势研究报告》。报告显示&#xff0c;2023 年上半年勒索软件检出数量继续下降、高级持续性威胁&#xff08;APT&a…...

MySQL ——多表连接查询

一、&#xff08;左、右和全&#xff09;连接概念 内连接&#xff1a; 假设A和B表进行连接&#xff0c;使用内连接的话&#xff0c;凡是A表和B表能够匹配上的记录查询出来。A和B两张表没有主付之分&#xff0c;两张表是平等的。 关键字&#xff1a;inner join on 语句&#xf…...

前沿技术 --> 待定

一、可会可不会 1.1如何优雅的编写技术文档 网址&#xff1a; 如何优雅的编写技术文档&#xff1f; - YouTube...

Linux定时python脚本(crontab版本)

1.0 使用Linux系统命令 crontab 自带的定时命令2.0 crontab的使用 2.1 添加定时任务 crontab -e2.2 查看定时任务的完成情况 2.2.1 查看日志 tail -f /var/log/syslog | grep CRON 2.2.2 任务执行情况 grep CRON /var/log/syslog 2.3 定时任务的规则 每隔一分钟执行一次…...

修改 Ubuntu .cache 和 pip cache 默认路径

修改 Ubuntu .cache 和 pip cache 默认路径 非常不建议修改 .cache 默认路径&#xff0c;除非你知道修改后的影响。 执行下面命令进行修改&#xff0c; vi /root/.bashrc--- 追加 export XDG_CACHE_HOME/u01/.cache export PIP_CACHE_DIR/u01/.cache ---完结&#xff01;...

【Java SE】Lambda表达式

目录 ♫什么是Lambda表达式 ♫Lambda表达式的语法 ♫函数式接口 ♫Lambda表达式的使用 ♫变量捕获 ♫ Lambda表达式在集合中的使用 ♪Collection的foreach()&#xff1a; ♪List的sort()&#xff1a; ♪Map的foreach() ♫什么是Lambda表达式 Lambda 表达式是 Java SE 8中一个…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...