LeetCode377. 组合总和 Ⅳ
377. 组合总和 Ⅳ
文章目录
- [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)
- 一、题目
- 二、题解
- 方法一:完全背包一维数组
- 动态规划思路
- 代码分析
- 方法二:动态规划二维数组
一、题目
给你一个由 不同 整数组成的数组 nums
,和一个目标整数 target
。请你从 nums
中找出并返回总和为 target
的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1:
输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:
输入:nums = [9], target = 3
输出:0
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums
中的所有元素 互不相同1 <= target <= 1000
进阶:如果给定的数组中含有负数会发生什么?问题会产生何种变化?如果允许负数出现,需要向题目中添加哪些限制条件?
二、题解
这道题要求我们找出由给定数组 nums
中的不同元素组成的总和等于 target
的组合个数,说是组合,其实实质上是排列,我在这篇文章里讲述了关于排列组合的区别并且手写了动态规划过程:https://blog.csdn.net/m0_61843614/article/details/132745696。
方法一:完全背包一维数组
动态规划思路
定义一个一维数组 dp
,其中 dp[i]
表示总和为 i
的组合个数。
我们的目标是计算 dp[target]
,也就是总和为 target
的组合个数。为了计算 dp[target]
,可以考虑如下的思路:
-
初始化一个长度为
target + 1
的数组dp
,并将其所有元素初始化为0。dp[i]
表示总和为i
的组合个数。 -
由于组合的元素可以重复使用,我们可以遍历数组
nums
中的每个元素,并尝试将其加入到总和为i
的组合中。 -
对于每个元素
nums[j]
,我们可以检查dp[i - nums[j]]
,它表示总和为i - nums[j]
的组合个数。我们可以将dp[i - nums[j]]
加到dp[i]
上,表示将nums[j]
加入到当前组合中。 -
重复上述步骤,直到遍历完数组
nums
中的所有元素。 -
最终,
dp[target]
就是我们要求的答案,表示总和为target
的组合个数。
代码分析
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<long long> dp(target + 1, 0);dp[0] = 1; // 初始化,总和为0的组合个数为1for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {if (nums[j] <= i && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] = dp[i] + dp[i - nums[j]]; // 更新 dp[i]}}}return dp[target];}
};
现在我逐步解释代码的各个部分:
-
我们定义了一个一维数组
dp
,长度为target + 1
,并将所有元素初始化为0。 -
初始化
dp[0]
为1,因为总和为0的组合只有一种方式,就是什么都不选。 -
使用两个嵌套的循环,外层循环遍历所有可能的总和
i
,内层循环遍历数组nums
中的所有元素。 -
在内层循环中,我们检查当前元素
nums[j]
是否小于等于i
,如果是,就说明可以将nums[j]
加入到总和为i
的组合中。 -
如果
dp[i]
的值还没有越界(小于INT_MAX - dp[i - nums[j]]
),则将dp[i - nums[j]]
的值加到dp[i]
上,表示将nums[j]
加入到当前组合中。 -
最终,返回
dp[target]
,即总和为target
的组合个数。
方法二:动态规划二维数组
先给出代码:
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {//dp[j][i]意义是背包容量为i的情况下,最后一个加入的数字是从nums[0]到nums[i]之间的方法的总数vector<vector<long long>> dp(nums.size(), vector<long long>(target + 1, 0));dp[0][0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {if (j > 0) {dp[j][i] = dp[j - 1][i];}if (i >= nums[j] && dp[j][i] < INT_MAX - dp[nums.size() - 1][i - nums[j]]) {dp[j][i] += dp[nums.size() - 1][i - nums[j]];}}}return dp[nums.size() - 1][target];}
};
- 动态规划思路
这个问题的目标是找出总和为 target
的元素组合的个数。首先,让我们定义一个二维数组 dp
,其中 dp[j][i]
意义是背包容量为i的情况下,最后一个加入的数字是从nums[0]
到nums[i]
之间的方法的总数。我们的目标是求 dp[nums.size() - 1][target]
,即使用所有的元素构成和为 target
的排列的个数。
- 初始化
首先,我们初始化 dp
数组,将所有元素都初始化为 0。然后我们设置 dp[0][0] = 1
,这是因为在前 0 个元素中,构成和为 0 的组合有一种方式,即不选择任何元素。
- 填充动态规划数组
接下来,我们使用两个嵌套循环来填充 dp
数组。外层循环 i
表示考虑前 i
个元素,内层循环 j
表示目标和为 j
。
-
如果
j < nums[i]
,意味着当前的元素nums[i]
太大,不能加入组合中,所以我们将dp[i][j]
设置为dp[i-1][j]
,表示不选择当前元素时的组合数,继承上一行的值。 -
如果
j >= nums[i]
,意味着当前的元素nums[i]
可以加入组合中。我们需要考虑两种情况:- 不选择当前元素,即
dp[i][j] = dp[i-1][j]
。 - 选择当前元素,即
dp[i][j] += dp[i][j - nums[i]]
,这里的dp[i][j - nums[i]]
表示在考虑前i
个元素,和为j - nums[i]
的组合数。
- 不选择当前元素,即
最终,dp[nums.size() - 1][target]
就代表了使用所有元素构成和为 target
的组合的个数。
- 返回结果
最后,我们返回 dp[nums.size() - 1][target]
即可得到答案。
相关文章:
LeetCode377. 组合总和 Ⅳ
377. 组合总和 Ⅳ 文章目录 [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)一、题目二、题解方法一:完全背包一维数组动态规划思路代码分析 方法二:动态规划二维数组 一、题目 给你一个由 不同 整数组成的数组 nums ࿰…...
QT将数据写入文件,日志记录
项目场景: 在QT应用中,有时候需要将错误信息记录在log文件里面,或者需要将数据输出到文件中进行比对查看使用。 创建log文件,如果文件存在则不创建 QDir dir(QCoreApplication::applicationDirPath()"/recv_data");if(…...
vue2与vue3的使用区别与组件通信
1. 脚手架创建项目的区别: vue2: vue init webpack “项目名称”vue3: vue create “项目名称” 或者vue3一般与vite结合使用: npm create vitelatest yarn create vite2. template中结构 vue2: template下只有一个元素节点 <template><div><div…...
亚信科技与中国信通院达成全方位、跨领域战略合作
9月11日,亚信科技(中国)有限公司「简称:亚信科技」与中国信息通信研究院「简称:中国信通院」在京达成战略合作,双方将在关键技术研发、产业链协同等方面展开全方位、跨领域、跨行业深度合作,共促…...
华为Linux系统开发工程师面试
在Linux系统开发工程师的面试中,你可能会遇到以下一些问题: 在同一个网站中,当客户访问的时候,会出现有的页面访问的速度快而有的慢,系统和服务完全正常、网络带宽正常,你如何诊断这个问题?你以…...
Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题
Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题 文章目录 Qt利用QTime实现sleep效果分时调用串口下发报文解决串口下发给下位机后产生的粘包问题现象解决方法 现象 当有多包数据需要连续下发给下位机时,比如下载数据等&#x…...
人工智能:神经细胞模型到神经网络模型
人工智能领域中的重要流派之一是:从神经细胞模型(Neural Cell Model)到神经网络模型(Neural Network Model)。 一、神经细胞模型 第一个人工神经细胞模型是“MP”模型,它是由麦卡洛克、匹茨合作࿰…...
Redisson分布式锁实战
实战来源 此问题基于电商 这周遇见这么一个问题,简略的说一下 由MQ发布了两个消息,一个是订单新增,一个是订单状态变更 由于直接付款之后,这两个消息的发布时间不分先后,可能会造成两种情况,1、订单状态变更…...
JavaScript中循环遍历数组、跳出循环和继续循环
循环遍历数组 上个文章我们简单的介绍for循环,接下来,我们使用for循环去读取数据的数据,之前我们写过这样的一个数组,如下: const ITshareArray ["张三","二愣子","2033-1997","…...
Java——》Synchronized和Lock区别
推荐链接: 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...
JDK20 + SpringBoot 3.1.0 + JdbcTemplate 使用
JDK20 SpringBoot 3.1.0 JdbcTemplate 使用 一.测试数据库 Postgres二.SpringBoot项目1.Pom 依赖2.配置文件3.启动类4.数据源配置类5.实体对象类包装类6.测试用实体对象1.基类2.扩展类 7.测试类 通过 JdbcTemplate 直接执行 SQL 语句,结合源码动态编译即可方便实现…...
CTFhub_SSRF靶场教程
CTFhub SSRF 题目 1. Bypass 1.1 URL Bypass 请求的URL中必须包含http://notfound.ctfhub.com,来尝试利用URL的一些特殊地方绕过这个限制吧 1.利用?绕过限制urlhttps://www.baidu.com?www.xxxx.me 2.利用绕过限制urlhttps://www.baidu.comwww.xxxx.me 3.利用斜…...
【华为OD机试】单词接龙【2023 B卷|100分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述: 单词接龙的规则是:可用于接龙的单词首字母必须要前一个单词的尾字母相同; 当存在多个首字母相同的单词时,取长度最长的单词,如果长度也相等, 则取字典序最小的单词;已经参与接龙…...
如何优雅的实现无侵入性参数校验之spring-boot-starter-validation
在开发过程中,参数校验是一个非常重要的环节。但是,传统的参数校验方法往往需要在代码中手动添加大量的 if-else 语句,这不仅繁琐,而且容易出错。为了解决这个问题,我们可以使用无侵入性参数校验的方式来简化代码并提高…...
企业架构LNMP学习笔记27
Keepalived的配置补充: 脑裂(裂脑):vip出现在了多台机器上。网络不通畅,禁用了数据包,主备服务器没法通讯,造成备服务器认为主服务器不可用,绑定VIP,主服务器VIP不会释放…...
品牌策划经理工作内容|工作职责|品牌策划经理做什么?
一位美国作家曾说过“品牌是一系列期望、记忆、故事和关系,他们共同构成了消费者最终原则一个产品或者服务的原因。” 所以,品牌经理这个岗位主要是创造感知价值主张,激发消费者购买这个品牌后带来的感知价值,这种回报的本质相对…...
【设计模式】三、概述分类+单例模式
文章目录 概述设计模式类型 单例模式饿汉式(静态常量)饿汉式(静态代码块)懒汉式(线程不安全)懒汉式(线程安全,同步方法)懒汉式(线程安全,同步代码块)双重检查静态内部类枚举单例模式在 JDK 应用的源码分析 …...
手把手教学 Springboot+ftp+下载图片
简单教学,复制即用的Ftp下载图片 引入配置包 <dependency><groupId>commons-fileupload</groupId><artifactId>commons-fileupload</artifactId><version>1.3.1</version></dependency><dependency><grou…...
LaaS LLM as a service
LaaS LLM as a service 核心构成GPT 产业链如何进行商业化LLM(Large Language Model) 发展和趋势LLM(Large Language Model) 对于行业公司的分层LLM(Large Language Model) 的机遇和挑战 LaaS LLM as a service 核心构成 计算:算力模型:算法输入&…...
数据结构与算法(一)数组的相关概念和底层java实现
一、前言 从今天开始,笔者也开始从0学习数据结构和算法,但是因为这次学习比较捉急,所以记录的内容并不会过于详细,会从基础和底层代码实现以及力扣相关题目去写相关的文章,对于详细的概念并不会过多讲解 二、数组基础…...
歌曲推荐《最佳损友》
最佳损友 陈奕迅演唱歌曲 《最佳损友》是陈奕迅演唱的一首粤语歌曲,由黄伟文作词,Eric Kwok(郭伟亮)作曲。收录于专辑《Life Continues》中,发行于2006年6月15日。 2006年12月26日,该曲获得2006香港新城…...
多元共进|科技促进艺术发展,助力文化传承
科技发展助力文化和艺术的传播 融合传统与创新,碰撞独特魅力 一起来了解 2023 Google 开发者大会上 谷歌如何依托科技创新 推动艺术与文化连接 传承和弘扬传统文化 自 2011 年成立以来,谷歌艺术与文化致力于提供体验艺术和文化的新方式,从生成…...
Java集合(Collection、Iterator、Map、Collections)概述——Java第十三讲
前言 本讲我们将继续来讲解Java的其他重要知识点——Java集合。Java集合框架是Java编程语言中一个重要的部分,它提供了一套预定义的类和接口,供程序员使用数据结构来存储和操作一组对象。Java集合框架主要包括两种类型:一种是集合(Collection),存储一个元素列表,…...
topscoding主题库模板题
目录 模板题 【模板题】分因数(P1101) 【模板题】区间素数 III(P1113) 进制转换 III (任意转任意) (P2463) AB Problem(高精度加法) A-B Problem(高精度减法&…...
Linux--进程间通讯--FIFO(open打开)
1. 什么是FIFO FIFO命名管道,也叫有名管道,来区分管道pipe。管道pipe只能用于有血缘关系的进程间通信,但通过FIFO可以实现不相关的进程之间交换数据。FIFO是Linux基础文件类型中的一种,但是FIFO文件在磁盘上没有数据块,…...
哪里可以了解轻量的工作流引擎?
如果想要实现高效率的办公,可以使用轻量的工作流引擎低代码技术平台。随着工作量日益繁重起来,传统的办公制作方式已经无法满足现实需要的,采用轻量级的表格制作工具,就能在无形中缓解办公压力,创造更高效、灵活、优质…...
lvs负载均衡、LVS集群部署
四:LVS集群部署 lvs给nginx做负载均衡项目 218lvs(DR 负载均衡器) yum -y install ipvsadm(安装这个工具来管理lvs) 设置VIP192.168.142.120 创建ipvsadm的文件用来存放lvs的规则 定义策略 ipvsadm -C //清空现有…...
如何应对核心员工提离职?
最近一年互联网行情不好,很多大厂都在裁员,但裁员并不是不要人做事了。原来你这个岗位10个人做,企业有钱赚养得起,现在企业不怎么赚钱了,只能养4个人了。那么会有六个被裁掉。这时候对企业价值最大的4个人会被留下。也…...
建站系列(八)--- 本地开发环境搭建(WNMP)
目录 相关系列文章前言一、准备工作二、Nginx安装三、MySQL安装四、PHP安装及Nginx配置五、总结 相关系列文章 建站系列(一)— 网站基本常识 建站系列(二)— 域名、IP地址、URL、端口详解 建站系列(三)— …...
21天学会C++:Day8----范围for与nullptr
目录 编辑 1. 范围for 2. nullptr 1. 范围for 我们在写C语言循环遍历代码的时候,无论是用 for循环,while循环都需要考虑循环的起始条件,循环变量的递增逻辑,循环的结束条件。麻烦不说还可能会出错。 int main() {int arr[]…...
wordpress 官方网站/怎么做公司网站推广
问题描述 所需的包在mavenCentral中没有,但又需要这样的包(有可能为另一个项目打成的jar包) 解决方法 方法一: 创建本地maven(或gradle)仓库,把所需的jar放入仓库中,通过mavenLoc…...
网站建设2017国内排行/网站推广公司大家好
基于你说的情况,我只是猜想的是,肯定是报错了,不然定时任务不会无缘无故停下,只是呢,这个报错你们没有发现罢了你们run方法里应该有一些异常Exception捕获,但是没有捕获错误,也就是Error&#x…...
wordpress4.0.6 漏洞/收录排名好的发帖网站
2019年3月27日 ——ACM宣布,深度学习之父Yoshua Bengio, Yann LeCun, 以及Geoffrey Hinton获得了2018年的图灵奖,被称为“计算机领域的诺贝尔奖”。其中Yoshua Bengio是《深度学习》作者之一。 今天,深度学习已经成为了人工智能技术领域最重…...
wordpress默认管理员密码/百度搜图入口
node版本升级nvmnvmw覆盖安装第一次安装node,可以直接到官网下载安装程序直接安装就可以,但是安装后如何进行node的版本管理 发现网上也提供了node的版本管理工具: nvm nvm是MAC & Linux版本管理工具不适用于window nvmw nvmw是windo…...
罗琳做的网站/口碑营销的优势有哪些
参考:https://blog.csdn.net/lifei08108006/article/details/50417485这个结论正确吗?看二条命令:数据是:select * FROM test.orders where ceate_record_time > 2019结果:为什么会出现 2018 的字符串?s…...
ps做专业网站/连接交换
很多热爱游戏,有多年游戏经验的程序员们想要加入游戏行业。程序员在玩游戏的时候,可能会发现一个问题,虽然有着几年甚至十年以上的游戏经历,但是也许不了解或者根本不知道一款游戏是怎么做出来的。今天,力扣特别邀请了…...