力扣每日一题 6/30 记忆化搜索/动态规划
- 博客主页:誓则盟约
- 系列专栏:IT竞赛 专栏
- 关注博主,后期持续更新系列文章
- 如果有错误感谢请大家批评指出,及时修改
- 感谢大家点赞👍收藏⭐评论✍



494.目标和【中等】
题目:
给你一个非负整数数组 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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
分析问题:
设 nums 的元素和为 s,添加正号的元素之和为 p,添加负号的元素(绝对值)之和为 q,那么有
- p+q=s
- p-q=target
化简得:
- p = (s+target) / 2
- q = (s-target) / 2
我们找所有元素里面选取出来的元素和恰好为p的方案个数,那么这就变成了一道经典的0-1背包问题的变形,找恰好装capacity,求方案数/最大/最小价值和,capacity指的是容量,也就是这里的负数的和的绝对值。
那么我们就可以根据传统的0-1背包问题的求解过程来解题,带上cache数组以便达到记忆化的一个效果。

此处也可以进行进一步的优化,用一个二维数组f来替代递推函数dfs:
首先创建一个二维数组f,其中n表示数组的长度,target表示目标值,该数组用于记录不同状态下的结果。
然后将f[0][0]初始化为1,这是一个基础的起始条件。接下来通过两个嵌套循环进行计算。外层循环遍历一个名为nums的数组,其中的每个元素x代表物品的价值。内层循环遍历目标值target的所有可能取值。在循环内部,根据不同条件更新f数组的值。
- 如果c小于x,说明当前考虑的物品价值x大于当前的目标值c,无法选择该物品,所以f[i + 1][c]保持与f[i][c]相同。
- 如果c大于或等于x,那么f[i + 1][c]等于f[i][c]加上f[i][c - x],这表示在这种情况下,可以选择该物品,所以要将不选择该物品的情况(f[i][c])和选择该物品的情况(f[i][c - x])的结果相加。
最后,函数返回f[n][target],即最终在考虑了所有物品和目标值的情况下的结果。
代码实现:
优化前:
class Solution:def findTargetSumWays(self, nums: list[int], target: int) -> int:# p = (s+t) /2target += sum(nums)if target < 0 or target % 2:return 0target //=2n=len(nums)@cache # 保存记忆def dfs(i,c): # i是剩余多少个物品没装 c是当前背包剩余容量if i<0:return 1 if c==0 else 0if c < nums[i]:return dfs(i-1,c)return dfs(i-1,c)+dfs(i-1,c-nums[i])return dfs(n-1,target)
优化后:
class Solution:def findTargetSumWays(self, nums: list[int], target: int) -> int:# p = (s+t) /2target += sum(nums)if target < 0 or target % 2:return 0target //=2n=len(nums)f=[[0]*(target+1) for _ in range(n+1)]f[0][0]=1for i,x in enumerate(nums):for c in range(target+1):if c<x: f[i+1][c] = f[i][c]else: f[i+1][c] = f[i][c] + f[i][c-x]return f[n][target]

总结:
优化后代码详细解释:
target += sum(nums):将target值加上数组nums的元素总和,得到p的2倍。if target < 0 or target % 2::检查新的target值是否小于0或是否为奇数。如果是,则直接返回0,表示无法得到目标值。target //= 2:将target值除以2,得到用于后续计算的新值。n = len(nums):获取数组nums的长度。f = [[0] * (target + 1) for _ in range(n + 1)]:创建一个二维数组f,用于动态规划的计算。f[0][0] = 1:设置初始状态,即当没有元素且目标值为0时,有一种方法可以达到。- 通过两个嵌套循环进行动态规划计算:
- 外层循环
for i, x in enumerate(nums):遍历数组nums的每个元素。 - 内层循环
for c in range(target + 1):遍历所有可能的目标值。 - 在循环内部,根据当前元素
x和目标值c的关系更新f[i + 1][c]的值。如果c < x,则f[i + 1][c] = f[i][c],表示无法选择当前元素来达到目标值;如果c >= x,则f[i + 1][c] = f[i][c] + f[i][c - x],表示可以选择或不选择当前元素来达到目标值,将两种情况的方法数相加。
- 外层循环
- 最后,函数返回
f[n][target],即使用整个数组nums达到最终目标值的方法数。
考点:
- 动态规划的应用:通过构建二维数组来记录不同状态下的结果,根据状态转移方程进行计算。
- 对问题的数学转化:将原问题转化为通过加减运算得到特定值的问题,并进行了一些预处理和条件判断。
收获:
- 深入理解了动态规划的思想和应用方法,学会如何根据问题的特点构建合适的状态和状态转移方程。
- 提高了对问题进行数学分析和转化的能力,能够将复杂的问题简化为可计算的形式。
- 增强了对数组操作和循环的熟练程度,能够灵活运用这些基本编程技巧来解决实际问题。

“对于我们的幸福来说,别人的看法在本质上来讲并不十分重要。”——《人生的智慧》
相关文章:
力扣每日一题 6/30 记忆化搜索/动态规划
博客主页:誓则盟约系列专栏:IT竞赛 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ 494.目标和【中等】 题目: 给你一个非负整数数组 nums 和一个…...
图像基础知识入门【图像概念不同图像格式】
图像基础知识入门【图像概念&不同图像格式】 最近有在处理图像转换,因此稍微补足了一下图像相关知识,特在此记录。下面汇总是我根据自己理解和网上查阅资料而来。如有错误,欢迎大家指正。 1 基础概念 像素/分辨率 像素(Pixel)ÿ…...
HP服务器基于SNMP-ilo4的硬件监控指标解读
监控易是一款功能全面的IT基础设施监控软件,它通过SNMP协议与HP服务器内置的ilo4远程管理卡进行通信,实现对HP服务器硬件状态的实时监控。本文将针对监控易中基于SNMP-ilo4的HP服务器硬件监控指标进行解读,帮助运维团队更好地理解和应用这些监…...
Android13系统导航栏添加音量加减键按钮功能
不知道为什么拿到芯片原厂发布给我们的Android13系统源码编译后,导航栏没有音量加减键,客户有反馈这个问题,所以特意加了一下,修改记录如下:frameworks/base目录下 commit 9cb2244d61a237cab03c540bfcca6e4fac2bea2c …...
普及GIS知识,推动产业发展
915 GIS节:普及GIS知识,推动产业发展 自2008年起,每年的9月15日被定为“GIS节”,这一特殊的节日由超图首次发起倡议,旨在打造一个普及和传播GIS(地理信息系统)知识的平台,促进大众对…...
第2章-Python编程基础
#本章目标 1,了解什么是计算机程序 2,了解什么是编程语言 3,了解编程语言的分类 4,了解静态语言与脚本语言的区别 5,掌握IPO程序编写方法 6,熟练应用输出函数print与输入函数input 7,掌握Python…...
LDO产品的基础知识解析
低压降稳压器 (LDO)是一种用于调节较高电压输入产生的输出电压的简单方法。在大多数情况下,低压降稳压器都易于设计和使用。然而,如今的现代应用都包括各种各样的模拟和数字系统,而有些系统和工作条件将决定哪种LDO最适合相关电路,…...
如何利用python画出AHP-SWOT的战略四边形(四象限图)
在企业或产业发展的相关论文分析中,常用到AHP-SWOT法进行定量分析,形成判断矩阵后,如何构造整洁的战略四边形是分析的最后一个环节,本文现将相关代码发布如下: import mpl_toolkits.axisartist as axisartist import …...
适用于智慧城市、智慧文旅等在线场景的轻量级3D数字人引擎MyAvatar简介
本人研发的国内首个纯面向web应用和小程序的轻量级3D虚拟人引擎MyAvatar。 功能简述 支持3D模型定制(写实或卡通风格均可,人物模型需实现绑定和变形)动画可以内置于模型中,也可以单独以glb或fbx格式导出并动态加载支持readyplay…...
Excel显示/隐藏批注按钮为什么是灰色?
在excel中,经常使用批注来加强数据信息的提示,有时候会把很多的批注显示出来,但是再想将它们隐藏起来,全选工作表后,“显示/隐藏批注”按钮是灰色的,不可用。 二、可操作方法 批注在excel、WPS表格中都是按…...
ArtTS系统能力-通知的学习(3.1)
上篇回顾: ArtTS语言基础类库-容器类库内容的学习(2.10.2) 本篇内容: ArtTS系统能力-通知的学习(3.1) 一、 知识储备 1. 基础类型通知 按内容分成四类: 类型描述NOTIFICATION_CONTENT_BASIC_TEXT普通文…...
Apollo9.0 PNC源码学习之Planning模块(三)—— public_road_planner
前面文章: (1)Apollo9.0 PNC源码学习之Planning模块(一)—— 规划概览 (2)Apollo9.0 PNC源码学习之Planning模块(二)—— planning_component 1 planning_interface_base 规划接口基类: planning\planning_interface_base\planner_base\planner.h #pragma once#in…...
【Elasticsearch】linux使用supervisor常驻Elasticsearch,centos6.10安装 supervisor
背景: linux服务器,CentOS 6操作系统,默认版本python2.6.6,避免安装过多的依赖不升级python 在网上查的资料python2.6.6兼容supervisor版本 3.1.3 安装supervisor 手动在python官网下载supervisor,并上传到服务器 下…...
推荐系统三十六式学习笔记:原理篇.模型融合14|一网打尽协同过滤、矩阵分解和线性模型
目录 从特征组合说起FM模型1.原理2.模型训练3.预测阶段4.一网打尽其他模型5.FFM 总结 在上一篇文章中,我们讲到了使用逻辑回归和梯度提升决策树组合的模型融合办法,用于CTR预估,给这个组合起了个名字,叫“辑度组合”。这对组合中&…...
如何使用mapXplore将SQLMap数据转储到关系型数据库中
关于mapXplore mapXplore是一款功能强大的SQLMap数据转储与管理工具,该工具基于模块化的理念开发,可以帮助广大研究人员将SQLMap数据提取出来,并转储到类似PostgreSQL或SQLite等关系型数据库中。 功能介绍 当前版本的mapXplore支持下列功能…...
JAVA设计模式-大集合数据拆分
背景 我们在做软件开发时,经常会遇到把大集合的数据,拆分成子集合处理。例如批量数据插入数据库时,一次大约插入5000条数据比较合理,但是有时候待插入的数据远远大于5000条。这时候就需要进行数据拆分。数据拆分基本逻辑并不复杂&…...
如何使用sr2t将你的安全扫描报告转换为表格格式
关于sr2t sr2t是一款针对安全扫描报告的格式转换工具,全称为“Scanning reports to tabular”,该工具可以获取扫描工具的输出文件,并将文件数据转换为表格格式,例如CSV、XLSX或文本表格等,能够为广大研究人员提供一个…...
ansible自动化运维,(2)ansible-playbook
三种常见的数据格式: XML:可扩展标记语言,用于数据交换和配置 JSON:对象标记法,主要用来数据交换或配置,不支持注释 YAML:不是一种标记语言,主要用来配置,大小写敏感&…...
一分钟学习数据安全—自主管理身份SSI分布式标识DID介绍
SSI标准化的两大支柱,一个是VC,之前简单介绍过,另一个就是DID。基本层次上,DID就是一种新型的全局唯一标识符,跟浏览器的URL没有什么不同。深层次上,DID是互联网分布式数字身份和PKI新层级的原子构件。 一…...
[单master节点k8s部署]11.服务service
service service是一个固定接入层,客户端 可以访问service的ip和端口,访问到service关联的后端pod,这个service工作依赖于dns服务(coredns) 每一个k8s节点上都有一个组件叫做kube-proxy,始终监视着apiser…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
