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

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 = targetpos + neg = sum,联立两式,可得2 * pos = target + sum,因此我们就可以进行第一个判定,target + sum不为偶数时,可知一定不能组合出target直接返回false即可。当为偶数时,我们要找到可以组成pospos = (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++版本)

题目描述 原题链接&#xff1a;494. 目标和 解题思路 &#xff08;1&#xff09;回溯法 本题的特点是nums中每个元素只能使用一次&#xff0c;分别试探加上nums[index]和减去nums[index]&#xff0c;然后递归的遍历下一个元素index 1。 class Solution { public:int res …...

MySQL-窗口函数

窗口函数概念常用窗口函数聚合窗口函数专用窗口函数语法OVER子句window_specwindow_name (命名窗口)partition_clause 分区order_clause 排序frame_clause 范围 &#xff08;指定窗口大小&#xff09;使用限制练习准备概念 窗口函数对一组查询执行类似于聚合的操作。然而&#…...

【C++设计模式】学习笔记(1):面向对象设计原则

目录 简介面向对象设计原则(1)依赖倒置原则(DIP)(2)开放封闭原则(OCP)(3)单一职责原则(SRP)(4)Liskov替换原则(LSP)(5)接口隔离原则(ISP)(6)优先使用对象组合,而不是类继承(7)封装变化点(8)针对接口编程,而不是针对实现编程结语简介 Hello! 非常感谢您阅读海…...

[测开篇]设计测试用例的方法如何正确描述Bug

​ 文章目录为什么测试人员要写测试用例&#xff1f;怎样设计测试用例&#xff1f;&#xff08;总的方面&#xff09;1.基于需求设计测试用例&#xff08;总的方面&#xff09; 2.页面&#xff08;总的方面&#xff09; 3.非功能性测试&#xff08;具体方面&#xff09; 4.1 等…...

设计模式学习笔记--单例、建造者、适配器、装饰、外观、组合

以下内容根据以下网址及相关视频整理&#xff1a;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 单选题&#xff1a;She has the face _________.2 单选题&#xff1a; The goals ________ he fought all his life no longer seemed important to him.3 单选题&#xff1a;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&#xfffd; (possibly of length 00). He performed the following operation several (possibly zero)…...

javassm超市在线配送管理系统

为了解决用户便捷地在网上购物&#xff0c;本文设计和开发了一个超市管理系统。本系统是基于web架构设计&#xff0c;SSM框架 &#xff0c;使用Mysql数据库管理&#xff0c;综合采用JSP模式来完成系统的相关功能。主要实现了管理员与用户的注册与登陆&#xff0c;个人中心、用户…...

Scratch少儿编程案例-多模式贪吃蛇(无尽和计时)

专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...

谷歌蜘蛛池怎么搭建?Google蜘蛛池可以帮助谷歌排名吗?

本文主要分享关于谷歌蜘蛛池的搭建疑问&#xff0c;以及Google对谷歌排名的影响到底有多大。 本文由光算创作&#xff0c;有可能会被剽窃和修改&#xff0c;我们佛系对待这种行为吧。 谷歌蜘蛛池怎么搭建&#xff1f; 答案是&#xff1a;需要一个内链外链体系复杂的站群系统…...

Kubernetes集群-部署Java项目

Kubernetes集群-部署Java项目&#xff08;SSG&#xff09; k8s部署项目java流程图 第一步 打包制作镜像 打包 java源码&#xff1a; application.properties #在有pom.xml的路径下执行 mvn clean package制作镜像&#xff1a; 将刚才打包后的文件夹传到&#xff0c;装有dock…...

English Learning - Day54 作业打卡 2023.2.8 周三

English Learning - Day54 作业打卡 2023.2.8 周三引言1. 就算你不喜欢喝酒&#xff0c;也请尝一杯吧。2. 便纵有千种风情&#xff0c;更与何人说&#xff1f;——柳永《雨霖铃》 (来&#xff0c;挑战一下古诗词)3. 虽然忙&#xff0c;我也要参加会议。4. 无论发生什么&#xf…...

【Unity题】 1.矩阵旋转,欧拉旋转,四元数旋转各自的优缺点。2.StringBuilder和String的区别

1.矩阵旋转&#xff0c;欧拉旋转&#xff0c;四元数旋转各自的优缺点 矩阵旋转&#xff0c;欧拉旋转&#xff0c;四元数旋转是三种不同的旋转表示方法&#xff0c;下面是它们各自的优缺点&#xff1a; 矩阵旋转&#xff1a; 优点&#xff1a; 1.可以方便地实现复合旋转&…...

【C++面试问答】搞清楚深拷贝与浅拷贝的区别

问题 深拷贝和浅拷贝的区别是面试中的常见问题之一&#xff0c;对于不同的编程语言&#xff0c;这个问题的回答可能稍有差别&#xff0c;下面我们就来探索一下它们之间的异同吧。 先来看看在JavaScript对象的深拷贝与浅拷贝的区别&#xff1a; 浅拷贝&#xff1a;只是复制了…...

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;/*** --- 天…...

电影订票网站的设计与开发

技术&#xff1a;Java、JSP等摘要&#xff1a;随着科技的发展&#xff0c;时代的进步&#xff0c;互联网已经成为了人们生活中不可缺少的一部分&#xff0c;网上购物已然是一种时代的象征。纵观市场&#xff0c;电影行业的发展尤为迅速&#xff0c;电影种类和数量的增多导致客流…...

seata【SAGA模式】代码实践(细节未必完全符合saga的配置,仅参考)

seata SAGA模式&#xff1a; 代码仍然是上一篇AT模式的代码&#xff1a;AT模式 不需要undo_log表 下面开始&#xff1a; 首先&#xff0c;saga模式依靠状态机的json文件来执行整个流程&#xff0c;其中的开始节点的服务即TM&#xff0c;然后状态机需要依靠三张表&#xff0…...

面试题:Java锁机制

java对象包含了三个部分&#xff1a;对象头&#xff0c;实例数据和对齐填充。对象头又存放了&#xff1a;markWord和class point。classpoint &#xff1a;指向方法区&#xff0c;当前对象的类信息数据。markword&#xff1a;存储了很多和当前对象运行时的数据&#xff1a;例如…...

Springboot Web开发

文章目录一. 静态资源访问1. 配置静态资源访问前缀2. 修改默认静态资源存放目录3. Webjars4. 欢迎页支持5. 自定义Favicon二. 请求处理1. 路径变量2. 请求头处理3. 查询字符串处理4. 获取Cookie的值5. 获取请求体的值6. 获取请求域中的数据7. 矩阵变量一. 静态资源访问 只要静…...

分布式事务 | 使用DTM 的Saga 模式

DTM 简介前面章节提及的MassTransit、dotnetcore/CAP都提供了分布式事务的处理能力&#xff0c;但也仅局限于Saga和本地消息表模式的实现。那有没有一个独立的分布式事务解决方案&#xff0c;涵盖多种分布式事务处理模式&#xff0c;如Saga、TCC、XA模式等。有&#xff0c;目前…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...