目标和(DP)

给你一个非负整数数组 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

DP:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int total = 0;for(int n : nums){total += n;}if((total + target) % 2 != 0 || total < abs(target)){return 0;}int sub = (total + target) / 2;vector<int> dp(sub + 1, 0);dp[0] = 1;for(int n : nums){for(int j = sub; j >= n; j--){dp[j] += dp[j - n];}}return dp[sub];}};

(total + target) % 2 != 0

如果 total + target 是奇数,那么无法将它分割成两部分,返回 0


nums 划分为两个子集:一个子集 P 代表带正号的部分。另一个子集 N 代表带负号的部分。

根据题目要求,这两个子集满足:

  • P − N=target
  • P + N = sum(nums)

通过这两个方程,我们可以推导出 P 的值:

  • P =(sum(nums) + target) / 2

为了确保 P 是一个整数,(sum(nums) + target) 必须是偶数。如果 (sum(nums) + target) 是奇数,那么 P 就会是一个小数,在这种情况下,问题无解,直接返回 0

total < abs(target)

如果 total 小于 target 的绝对值,则无法通过 +- 来组合出 target,所以直接返回 0

这就变成了一个子集和问题:计算所有可以构成和为 sub 的子集数目。

定义dp[i] 表示可以组成和为 i 的子集数目。

初始时,dp[0] = 1,表示可以通过一个空集来组成和为 0 的子集。所有其他 dp[i](对于 i > 0)都为 0,因为还没有计算任何子集。

为什么从 sub 开始倒序遍历?

  • 为了避免当前的元素 n 被重复使用。假设我们正在处理元素 n 并且当前正在更新 dp[j],如果我们从 dp[sub] 开始遍历并往下计算,就可以确保每次计算时,dp[j - n] 只会使用上一轮的值。
  • 如果我们从小到大遍历,可能会在同一轮循环中多次使用同一个元素 n,这会导致错误的计算。

dp[j] += dp[j - n] 的含义:

  • dp[j - n] 代表当前元素 n 加入之前,可以组成和为 j - n 的子集数量。
  • 加上 n 后,和变为 j,因此可以通过将 dp[j - n] 加到 dp[j] 上,来表示有多少个子集和为 j
  • 换句话说,dp[j] 就是之前可以组成和为 j - n 的子集数目与当前元素 n 组合后组成和为 j 的子集数目的和。

举个例子:

nums = [1, 2, 3], sub = 4,那么 dp 数组初始化为:

dp = [1, 0, 0, 0, 0]  

第一次循环,n = 1

dp[4] += dp[4 - 1] = dp[3]dp[4] = 0

dp[3] += dp[3 - 1] = dp[2]dp[3] = 0

dp[2] += dp[2 - 1] = dp[1]dp[2] = 0

dp[1] += dp[1 - 1] = dp[0]dp[1] = 1

第二次循环,n = 2

dp[4] += dp[4 - 2] = dp[2]dp[4] = 0

dp[3] += dp[3 - 2] = dp[1]dp[3] = 1

dp[2] += dp[2 - 2] = dp[0]dp[2] = 1

第三次循环,n = 3

dp[4] += dp[4 - 3] = dp[1]dp[4] = 1

dp[3] += dp[3 - 3] = dp[0]dp[3] = 2

最后:

dp = [1, 1, 1, 2, 1] ,    dp[sub] = dp[4] = 1

DFS:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {return dfs(nums, target, 0, 0);}int dfs(vector<int>& nums, int target, int i, int sum){if(i == nums.size()){return sum == target ? 1 : 0;}int a = dfs(nums, target, i + 1, sum + nums[i]);int b = dfs(nums, target, i + 1, sum - nums[i]);return a + b;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯备考——算法

一、排序 冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序 二、枚举 三、二分查找与二分答案 四、搜索&#xff08;DFS&#xff09; DFS&#xff08;DFS基础、回溯、剪枝、记忆化&#xff09; 1.DFS算法&#xff08;深度优先搜索算法&#xff09; 深度优先搜…

【网络面试篇】其他面试题——Cookie、Session、DNS、CDN、SSL/TLS、加密概念

目录 一、HTTP 相关问题 1. Cookie 和 Session 是什么&#xff1f; &#xff08;1&#xff09;Cookie &#xff08;2&#xff09;Session 2. Cookie 的工作原理&#xff1f; 3. Session 的工作原理&#xff1f; 4. Cookie 和 Session 有什么区别&#xff1f; 二、其他问…

隧道论文阅读2-采用无人融合扫描数据的基于深度学习的垂直型隧道三维数字损伤图

目前存在的问题&#xff1a; 需要开发新的无人测量系统测量垂直隧道图像数据量巨大&#xff0c;基于深度学习完成损伤评估跟踪获取图像位置的困难&#xff0c;对大型基础设施感兴趣区域(roi)的2d和3d地图建立进行了研究&#xff0c;对整个目标结构的损伤定位仍然具有挑战性。为…

CCF-A类 HPCA 2025 重磅揭晓:录取数据公布

近日&#xff0c;第31届国际计算机体系结构领域顶级会议HPCA (International Symposium on High Performance Computer Architecture) 正式发布了2025年会议的录用通知&#xff01;本届会议共收到了534 篇提交论文&#xff0c;其中&#xff0c;112篇论文被接收&#xff0c;整体…

Linux应用——线程池

1. 线程池要求 我们创建线程池的目的本质上是用空间换取时间&#xff0c;而我们选择于 C 的类内包装原生线程库的形式来创建&#xff0c;其具体实行逻辑如图 可以看到&#xff0c;整个线程池其实就是一个大型的 CP 模型&#xff0c;接下来我们来完成它 2. 整体模板 #pragma …

IDM扩展添加到Edge浏览器

IDM扩展添加到Edge浏览器 一般情况下&#xff0c;当安装IDM软件后&#xff0c;该软件将会自动将IDM Integration Module浏览器扩展安装到Edge浏览器上&#xff0c;但在某些情况下&#xff0c;需要我们手动安装&#xff0c;以下为手动安装步骤 手动安装IDM扩展到Edge浏览器 打…

docker 拉取MySQL8.0镜像以及安装

目录 一、docker安装MySQL镜像 搜索images 拉取MySQL镜像 二、数据挂载 在/root/mysql/conf中创建 *.cnf 文件 创建容器,将数据,日志,配置文件映射到本机 检查MySQL是否启动成功&#xff1a; 三、DBeaver数据库连接 问题一、Public Key Retrieval is not allowed 问题…

深入探索Waymo自动驾驶技术发展:从DARPA挑战赛到第五代系统的突破

引言 自动驾驶技术正引领着未来出行方式的革命&#xff0c;而Waymo作为全球自动驾驶领域的先锋&#xff0c;始终走在技术发展的最前沿。本文基于Waymo联席CEO德米特里多尔戈夫&#xff08;Dmitri Dolgov&#xff09;在No Priors节目中的访谈&#xff0c;全面介绍Waymo的技术发展…

鸿蒙移动应用开发-------初始arkts

一. 什么是arkts ArkTS是HarmonyOS优选的主力应用开发语言。 ArkTS围绕应用开发在TypeScript&#xff08;简称TS&#xff09;生态基础上做了进一步扩展&#xff0c;保持了TS的基本风格&#xff0c;同时通过规范定义强化开发期静态检查和分析&#xff0c;提升程序执行稳定性和…

c++ 输入三条边 绘制三角形

安装图形库 参考 #include "graphics.h" // 就是需要引用这个图形库 #include <conio.h> #include <stdio.h> #include <math.h>// 判断是否可以构成三角形 int isTriangle(int a, int b, int c) {return (a b > c) && (a c >…

A20红色革命文物征集管理系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

Logrus入门

Logrus入门 1. 下载 go get github.com/sirupsen/logrus2. logrus常用方法 logrus.Debugln("Debugln") logrus.Infoln("Infoln") logrus.Warnln("Warnln") logrus.Errorln("Errorln") logrus.Println("Println")// 输出如…

pyspark入门基础详细讲解

1.前言介绍 学习目标&#xff1a;了解什么是Speak、PySpark&#xff0c;了解为什么学习PySpark&#xff0c;了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码&#xff0c;既可以在电脑上简单运行&#xff0c;进行数据分析处理&#xff0c;又可以把代码无缝…

权限管理练习2

1.在/home中创建一个名为 file1.txt 的文件&#xff0c;并设置权限为&#xff1a;所有者和组成员可以读写&#xff0c;但其他人只能读。 所有者和组成员可以读写 u rw- g rw- o r-- 2.在 /home 目录下创建一个名为 shared 的子目录&#xff0c;使得所有用户都可以进入&#…

面试经典 150 题:121,125

121. 买卖股票的最佳时机 【参考代码】 动态规划解决 class Solution { public:int maxProfit(vector<int>& prices) {int size prices.size();int min_price 99999, max_profit 0;for(int i0; i<size; i){if(prices[i] < min_price){min_price prices[i…

数据集划分

1、 sklearn玩具数据集介绍 数据量小&#xff0c;数据在sklearn库的本地&#xff0c;只要安装了sklearn&#xff0c;不用上网就可以获取 2 sklearn现实世界数据集介绍 数据量大&#xff0c;数据只能通过网络获取&#xff08;科学上网&#xff09; 3 sklearn加载玩具数据集 示…

图形几何之美系列:仿射变换矩阵之先转后偏

“在几何计算、图形渲染、动画、游戏开发等领域&#xff0c;常需要进行元素的平移、旋转、缩放等操作&#xff0c;一种广泛应用且简便的方法是使用仿射变换进行处理。相关的概念还有欧拉角、四元数等&#xff0c;四元数在图形学中主要用于解决旋转问题&#xff0c;特别是在三维…

刷题强训(day05) -- 游游的you、腐烂的苹果、孩子们的游戏(圆圈中最后剩下的数)

目录 1、游游的you 1.1 题目 1.2 思路 1.3 代码实现 2、腐烂的苹果 2.1 题目 2.2 思路 2.3 代码实现 3、孩子们的游戏(圆圈中最后剩下的数) 3.1 题目 3.2 思路 3.3 代码实现 3.3.1 环形链表 ​编辑3.3.2 动态规划 ​编辑 1、游游的you 1.1 题目 1.2 思路 根据题…

PyQt5超详细教程终篇

PyQt5超详细教程 前言 接&#xff1a; [【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;](【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;-CSDN博客) 建议把代码复制到pycahrm等IDE上面看实际效果&#xff0c;方便理…

并查集算法实现

模板 模板分为三大部分 初始化查询i的祖先合并i j(使他们祖先成为一个人) // 1 初始化 void init(int n) {for (int i 1; i < n; i)fa[i] i;//将该数的父节点定义为该数 }// 2 查询i的祖先 int find(int i) {if (i fa[i])return i;else{![查](../pic/并查集.png)fa[i]…