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

力扣每日一题 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 <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= 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]


 

总结:

优化后代码详细解释
  1. target += sum(nums):将target值加上数组nums的元素总和,得到p的2倍。
  2. if target < 0 or target % 2::检查新的target值是否小于0或是否为奇数。如果是,则直接返回0,表示无法得到目标值。
  3. target //= 2:将target值除以2,得到用于后续计算的新值。
  4. n = len(nums):获取数组nums的长度。
  5. f = [[0] * (target + 1) for _ in range(n + 1)]:创建一个二维数组f,用于动态规划的计算。
  6. f[0][0] = 1:设置初始状态,即当没有元素且目标值为0时,有一种方法可以达到。
  7. 通过两个嵌套循环进行动态规划计算:
    • 外层循环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],表示可以选择或不选择当前元素来达到目标值,将两种情况的方法数相加。
  8. 最后,函数返回f[n][target],即使用整个数组nums达到最终目标值的方法数。

考点

  1. 动态规划的应用:通过构建二维数组来记录不同状态下的结果,根据状态转移方程进行计算。
  2. 对问题的数学转化:将原问题转化为通过加减运算得到特定值的问题,并进行了一些预处理和条件判断。

收获

  1. 深入理解了动态规划的思想和应用方法,学会如何根据问题的特点构建合适的状态和状态转移方程。
  2. 提高了对问题进行数学分析和转化的能力,能够将复杂的问题简化为可计算的形式。
  3. 增强了对数组操作和循环的熟练程度,能够灵活运用这些基本编程技巧来解决实际问题。

 “对于我们的幸福来说,别人的看法在本质上来讲并不十分重要。”——《人生的智慧》

http://www.lryc.cn/news/387799.html

相关文章:

  • 图像基础知识入门【图像概念不同图像格式】
  • HP服务器基于SNMP-ilo4的硬件监控指标解读
  • Android13系统导航栏添加音量加减键按钮功能
  • 普及GIS知识,推动产业发展
  • 第2章-Python编程基础
  • LDO产品的基础知识解析
  • 如何利用python画出AHP-SWOT的战略四边形(四象限图)
  • 适用于智慧城市、智慧文旅等在线场景的轻量级3D数字人引擎MyAvatar简介
  • Excel显示/隐藏批注按钮为什么是灰色?
  • ArtTS系统能力-通知的学习(3.1)
  • Apollo9.0 PNC源码学习之Planning模块(三)—— public_road_planner
  • 【Elasticsearch】linux使用supervisor常驻Elasticsearch,centos6.10安装 supervisor
  • 推荐系统三十六式学习笔记:原理篇.模型融合14|一网打尽协同过滤、矩阵分解和线性模型
  • 如何使用mapXplore将SQLMap数据转储到关系型数据库中
  • JAVA设计模式-大集合数据拆分
  • 如何使用sr2t将你的安全扫描报告转换为表格格式
  • ansible自动化运维,(2)ansible-playbook
  • 一分钟学习数据安全—自主管理身份SSI分布式标识DID介绍
  • [单master节点k8s部署]11.服务service
  • ES6面试题——箭头函数和普通函数有什么区别
  • WordPress中文网址导航栏主题风格模版HaoWa
  • ThreadPoolExecutor基于ctl变量的声明周期管理
  • 运维锅总详解Prometheus
  • 深入解析Tomcat:Java Web服务器(上)
  • 【第9章】MyBatis-Plus持久层接口之SimpleQuery
  • 一文带你了解乐观锁和悲观锁的本质区别!
  • Android Studio环境搭建(4.03)和报错解决记录
  • 基于协同过滤的电影推荐与大数据分析的可视化系统
  • 修复vcruntime140.dll方法分享
  • PostgreSQL的系统视图pg_stat_wal_receiver