154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
题目描述



原题链接:494. 目标和
解题思路
(1)回溯法
本题的特点是nums中每个元素只能使用一次,分别试探加上nums[index]和减去nums[index],然后递归的遍历下一个元素index + 1。
class Solution {
public:int res = 0;void backtracking(vector<int>& nums, int target, int index) {if(index == nums.size()) {if(target == 0) res++;return ;}backtracking(nums, target - nums[index], index + 1);backtracking(nums, target + nums[index], index + 1);}int findTargetSumWays(vector<int>& nums, int target) {backtracking(nums, target, 0);return res;}
};
(2)动态规划
本题中的数都为非负数,目标要求是选取组成正数的数与负数的数,让其和为target,因此我们可以将这个题中的数划分为两个集合,一个是要组成正数的集合,设容量为pos,一个是要组成负数的集合,设容量为neg。
由题中要求可得pos - neg = target,pos + neg = sum,联立两式,可得2 * pos = target + sum,因此我们就可以进行第一个判定,当target + sum不为偶数时,可知一定不能组合出target直接返回false即可。当为偶数时,我们要找到可以组成pos(pos = (target + sum) / 2)的组合。问题就可以转变为,当背包容量为pos时,选取nums里的数,有多少种组合方式可填满背包。
- 动态规划五步曲:
(1)dp[j]含义: 装满背包容量为j的方式个数。
(2)递推公式: dp[j] += dp[j - nums[i]],装入nums[i]之前,容量为j - nums[i]时的方式个数dp[j - nums[i]],再加上装入nums[i]之后,容量为j时之前的方式个数dp[j],进而得到背包容量为j时,总的方式个数。
(3)dp数组初始化: dp[0] = 1,容量为0时,仅有一种方式可以成立,即选择数字0。
(4)遍历顺序: 先物品、再背包,内层按从大到小遍历的滚动数组。
(5)举例:
输入: nums: [1, 1, 1, 1, 1], S: 3
此时,正数最大为4,里面只有1,因此dp[j]长度为4。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sumNums = 0;for(int i = 0; i < nums.size(); i++) sumNums += nums[i];// target超过总和或者不满足pos为偶数的情况,直接返回0if(abs(target) > sumNums || (sumNums + target) % 2 != 0) return 0;int dp[10001] = {0};dp[0] = 1;int pos = (sumNums + target) / 2;for(int i = 0; i < nums.size(); i++) {for(int j = pos; j >= nums[i]; j--) {// 组合情况要累计dp[j] += dp[j - nums[i]];}}return dp[pos];}
};
参考文章:494. 目标和、目标和、目标和(详细C++代码动态规划详细思路分析)
相关文章:
154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
题目描述 原题链接:494. 目标和 解题思路 (1)回溯法 本题的特点是nums中每个元素只能使用一次,分别试探加上nums[index]和减去nums[index],然后递归的遍历下一个元素index 1。 class Solution { public:int res …...
MySQL-窗口函数
窗口函数概念常用窗口函数聚合窗口函数专用窗口函数语法OVER子句window_specwindow_name (命名窗口)partition_clause 分区order_clause 排序frame_clause 范围 (指定窗口大小)使用限制练习准备概念 窗口函数对一组查询执行类似于聚合的操作。然而&#…...
【C++设计模式】学习笔记(1):面向对象设计原则
目录 简介面向对象设计原则(1)依赖倒置原则(DIP)(2)开放封闭原则(OCP)(3)单一职责原则(SRP)(4)Liskov替换原则(LSP)(5)接口隔离原则(ISP)(6)优先使用对象组合,而不是类继承(7)封装变化点(8)针对接口编程,而不是针对实现编程结语简介 Hello! 非常感谢您阅读海…...
[测开篇]设计测试用例的方法如何正确描述Bug
文章目录为什么测试人员要写测试用例?怎样设计测试用例?(总的方面)1.基于需求设计测试用例(总的方面) 2.页面(总的方面) 3.非功能性测试(具体方面) 4.1 等…...
设计模式学习笔记--单例、建造者、适配器、装饰、外观、组合
以下内容根据以下网址及相关视频整理:Android设计模式之单例模式_谬谬清不给我取名字的博客-CSDN博客_android 单例模式 Android设计模式--单例模式的六种实现和单例模式讲解Volatile与Synchronized相关的并发_龙腾腾的博客-CSDN博客_android 单例 volatile java …...
English Learning - Day5 L1考前复习 2023.2.10 周五
English Learning - Day5 L1考前复习 2023.2.10 周五1 单选题:She has the face _________.2 单选题: The goals ________ he fought all his life no longer seemed important to him.3 单选题:Sales director is a position ______ communi…...
C. Prepend and Append
time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Timur initially had a binary string†† s� (possibly of length 00). He performed the following operation several (possibly zero)…...
javassm超市在线配送管理系统
为了解决用户便捷地在网上购物,本文设计和开发了一个超市管理系统。本系统是基于web架构设计,SSM框架 ,使用Mysql数据库管理,综合采用JSP模式来完成系统的相关功能。主要实现了管理员与用户的注册与登陆,个人中心、用户…...
Scratch少儿编程案例-多模式贪吃蛇(无尽和计时)
专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...
谷歌蜘蛛池怎么搭建?Google蜘蛛池可以帮助谷歌排名吗?
本文主要分享关于谷歌蜘蛛池的搭建疑问,以及Google对谷歌排名的影响到底有多大。 本文由光算创作,有可能会被剽窃和修改,我们佛系对待这种行为吧。 谷歌蜘蛛池怎么搭建? 答案是:需要一个内链外链体系复杂的站群系统…...
Kubernetes集群-部署Java项目
Kubernetes集群-部署Java项目(SSG) k8s部署项目java流程图 第一步 打包制作镜像 打包 java源码: application.properties #在有pom.xml的路径下执行 mvn clean package制作镜像: 将刚才打包后的文件夹传到,装有dock…...
English Learning - Day54 作业打卡 2023.2.8 周三
English Learning - Day54 作业打卡 2023.2.8 周三引言1. 就算你不喜欢喝酒,也请尝一杯吧。2. 便纵有千种风情,更与何人说?——柳永《雨霖铃》 (来,挑战一下古诗词)3. 虽然忙,我也要参加会议。4. 无论发生什么…...
【Unity题】 1.矩阵旋转,欧拉旋转,四元数旋转各自的优缺点。2.StringBuilder和String的区别
1.矩阵旋转,欧拉旋转,四元数旋转各自的优缺点 矩阵旋转,欧拉旋转,四元数旋转是三种不同的旋转表示方法,下面是它们各自的优缺点: 矩阵旋转: 优点: 1.可以方便地实现复合旋转&…...
【C++面试问答】搞清楚深拷贝与浅拷贝的区别
问题 深拷贝和浅拷贝的区别是面试中的常见问题之一,对于不同的编程语言,这个问题的回答可能稍有差别,下面我们就来探索一下它们之间的异同吧。 先来看看在JavaScript对象的深拷贝与浅拷贝的区别: 浅拷贝:只是复制了…...
day10_面向对象基础
今日内容 零、 复习昨日 一、面向对象的概念 二、面向对象编程 三、内存图 零、 复习昨日 见晨考题 每日一数组题 写一个方法 用于合并两个int类型的数组 合并法则如下 {1,2,5,8,9}{1,3,0}---->{1,2,5,8,9,1,3,0} package com.qf.array;import java.util.Arrays;/*** --- 天…...
电影订票网站的设计与开发
技术:Java、JSP等摘要:随着科技的发展,时代的进步,互联网已经成为了人们生活中不可缺少的一部分,网上购物已然是一种时代的象征。纵观市场,电影行业的发展尤为迅速,电影种类和数量的增多导致客流…...
seata【SAGA模式】代码实践(细节未必完全符合saga的配置,仅参考)
seata SAGA模式: 代码仍然是上一篇AT模式的代码:AT模式 不需要undo_log表 下面开始: 首先,saga模式依靠状态机的json文件来执行整个流程,其中的开始节点的服务即TM,然后状态机需要依靠三张表࿰…...
面试题:Java锁机制
java对象包含了三个部分:对象头,实例数据和对齐填充。对象头又存放了:markWord和class point。classpoint :指向方法区,当前对象的类信息数据。markword:存储了很多和当前对象运行时的数据:例如…...
Springboot Web开发
文章目录一. 静态资源访问1. 配置静态资源访问前缀2. 修改默认静态资源存放目录3. Webjars4. 欢迎页支持5. 自定义Favicon二. 请求处理1. 路径变量2. 请求头处理3. 查询字符串处理4. 获取Cookie的值5. 获取请求体的值6. 获取请求域中的数据7. 矩阵变量一. 静态资源访问 只要静…...
分布式事务 | 使用DTM 的Saga 模式
DTM 简介前面章节提及的MassTransit、dotnetcore/CAP都提供了分布式事务的处理能力,但也仅局限于Saga和本地消息表模式的实现。那有没有一个独立的分布式事务解决方案,涵盖多种分布式事务处理模式,如Saga、TCC、XA模式等。有,目前…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
