​LeetCode刷题实战377:组合总和 Ⅳ

news/2024/2/21 10:36:55

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 组合总和 Ⅳ,我们先来看题面:

https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

给你一个由 不同 整数组成的数组 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

解题

动态规划

本题第一眼以为是dfs,但是实在想不出来下标怎么处理

dp数组的意义:dp[i]代表'target = i'时的组合数目,显然此时dp数组的初始化长度为target+1。

遍历规则:1 <= i <= target, ++i,target值从小到大。内层遍历是遍历nums数组。

更新规则:dp[i] += dp[i-num],隐含的含义是若当前i >= num,那么可以在dp[i-num]加入num,组合为一个完整组合。

边界条件:dp[0] = 1,当i == num,代表本身数字是一个组合,因此dp[0]需等于1。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {// dp[i]:target为i时的组合数目vector<int> dp(target+1, 0);dp[0] = 1;for(int i = 1; i < target + 1;++i){for(auto num:nums){if(num <= i && dp[i-num] < INT_MAX - dp[i]) // 防止越界dp[i] += dp[i - num];}}return dp[target];}
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-360题汇总,希望对你有点帮助!

LeetCode刷题实战361:轰炸敌人

LeetCode刷题实战362:敲击计数器

LeetCode刷题实战363:矩形区域不超过 K 的最大数值和

LeetCode刷题实战364:加权嵌套序列和 II

LeetCode刷题实战365:水壶问题

LeetCode刷题实战366:寻找二叉树的叶子节点

LeetCode刷题实战367:有效的完全平方数

LeetCode刷题实战368:最大整除子集数

LeetCode刷题实战369:给单链表加一

LeetCode刷题实战370:区间加法

LeetCode刷题实战371:两整数之和

LeetCode刷题实战372:超级次方

LeetCode刷题实战373:查找和最小的K对数字

LeetCode刷题实战374:猜数字大小

LeetCode刷题实战375:猜数字大小 II

LeetCode刷题实战376:摆动序列


http://www.ppmy.cn/news/276777.html

相关文章

v语言怎么玩

直接上github: https://github.com/vlang/v 前戏 大概是在6月份的时候,在github上看到了这个玩意,我以为是??? V字仇杀队 ?? 我下意识的去查了一下有没有人在讨论这个语言,但是关于这货的在国内讨论比较少 噱头如下: Simplicity: the language can be learned in less tha…

V 字仇杀队(V for Vendetta)

如果 50 年后有人撰写世界电影的编年史&#xff0c; 2006 年的代表电影应该有 《V 字仇杀队》的一席之地。 这部电影注定要和《1984》扯上关系&#xff0c;那个无所不在的”伦敦之声”让你没办法不和”老大哥”联想在一起; 没有人知道真相是怎样&#xff0c;真理掌握在少数人手…

电影之记忆1:V字仇杀队

讲述一个时代的政治体系的由来&#xff01; 主人公在里面是政治的悲剧产物&#xff01; 电影讲述了通过个人力量唤醒公众推翻政党的故事&#xff01; 很喜欢主人公说话的语气&#xff01;给我印象非常深&#xff01; 希望你喜欢&#xff01;希望看过后给点评价&#xff01;

九度oj 题目1364:v字仇杀队

题目描述&#xff1a; 最近玄影游侠看了一部非常好看的电影&#xff0c;叫做《v字仇杀队》。下面是这部电影的主角v&#xff1a; 它想说明的一个问题就是&#xff0c;你现在所想的真的是你自己内心所想的吗&#xff1f;还是别人&#xff0c;社会让你这么想的&#xff1f;你要有…

九度笔记之 1364:v字仇杀队

题目1364&#xff1a;v字仇杀队 时间限制&#xff1a;1 秒 内存限制&#xff1a;32 兆 特殊判题&#xff1a;否 提交&#xff1a;302 解决&#xff1a;109 题目描述&#xff1a; v整整策划了一年炸掉英国政府的大楼来推翻独裁统治&#xff0c;在这期间&#xff0c;v遇到了一个问…

九度 1364 v字仇杀队

http://ac.jobdu.com/problem.php?id1364 经典01背包&#xff0c;没有用空间逆序优化。 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 int S,C; 5 int force[102]; 6 int space[102]; 7 int mat[102][1002]; 8 int max(int a,int b…

风青杨:如何解读央视播放《V字仇杀队》?

12月14日晚&#xff0c;CCTV-6破天荒播出电影《V字别动队》&#xff0c;此举在微博上引起热议。有网友甚至惊呼“这样的电影能在央视上映&#xff0c;我一度怀疑自己是在做梦。”这部曾经一度禁播的电影自上映以来首次在大陆公映&#xff0c;该片中的经典台词“人民不应该害怕政…

V字仇杀队精彩简介_免费下载

1、英国历史上有个人叫盖伊福克斯试图炸毁议会大厦&#xff0c;最终被判处绞刑。有一个男人戴上盖伊的面具&#xff0c;全副武装后出门了。与此同时伊薇哈蒙德也打算出门&#xff0c;听到节目主持人一味的洗脑而厌烦的伊薇关上电视&#xff0c;发现已经过了宵禁时间&#xff0c…

我的GIT练习ONE

目录 前言 GIT安装教程 Git作者 GIT优点 GIT缺点 为什么要使用 Git GIT练习ONE 总结 前言 Git 是一个分布式版本控制及源代码管理工具;Git 可以为你的项目保存若干快照&#xff0c;以此来对整个项目进行版本管理 GIT安装教程 点击进入查看教程&#xff1a;点击进入 Gi…

Glibc——堆利用机制[拓展]

目录 1、什么是堆 2、使用动态分配的内存 3、系统调用brk和mmap 3.1 brk() 3.2 mmap() 4、多线程与Arena 5、维护多个堆 1、什么是堆 堆是每个程序被分配到的一块内存区域&#xff0c;和栈的区别主要在于堆内存是动态分配的。也就是说&#xff0c;程序可以从“heap“段请…

sed命令对文件内的指定字符串进行替换

目录 一、创建一个txt文件 二、替换每行第一个huawei为apple&#xff0c;第三个“/”后&#xff0c;不加参数就是只替换第一个 三、替换每行所有的xiaomi为iphone&#xff0c;第三个“/”后&#xff0c;加参数g就是替换所有 四、替换每行第二个redmi为potato&#xff0c;第…

乔春洋:主品牌与副品牌

乔春洋&#xff1a;主品牌与副品牌 许多企业在品牌不变的情况下&#xff0c;为自己的新产品起一个优美动听的小名&#xff0c;我们把这个小名叫作副品牌。副品牌在不少行业被广泛使用&#xff0c;而以家电业为最多。例如海尔电冰箱、洗衣机中的“小王子”、“大王子”、“…

CES 2015大会:智能家居或将竞相亮相

在去年于拉斯维加斯举办的CES 2014大会上&#xff0c;各场馆均广泛地展出了智能家居产品。而在名为Tech West科技的展会上&#xff0c;智能家居产品将拥有其专用展览空间&#xff0c;并将此作为位于金沙酒店一个新会议区的一部分。虽然我们仍会在全城各处会见各种其他智能家居供…

共享AI智慧生活 国美智能打造零售生态核心竞争力

7月10日&#xff0c;36氪举办的“明质本质远质——2018商业新生态峰会”在北京举办&#xff0c;本届商业新生态峰会主题为“质”&#xff0c;吸引了众多零售行业企业代表及产业链大咖。峰会上&#xff0c;新商业领袖们开启智慧碰撞&#xff0c;共同拨开商业本质&#xff0c;为新…

嵌入式成长轨迹0 嵌入式展望与学习路线

【引&#xff1a;智能家居概念】 随着家庭自动化技术的发展&#xff0c;很多以前出现在科幻小说中的场景已经变为现实&#xff1a;只要说“看电视”就可以把电视打开&#xff0c;拉上窗帘&#xff0c;房间的光线逐渐调整到最适宜看电视的程度……或者&#xff0c;在回家的路上&…

CAEE广东家电配件展-家电零部件展——CAEE家电与电子电器供应链博览会

CAEE家电与电子电器供应链博览会(China International Appliance & Electronics Supply Chain Expo)暨中国国际家电零部件、材料、家电配件、家电技术设备展览会将于2022年上半年和下半年&#xff0c;分别在广东、上海(长三角)、合肥、青岛中国四大家电产业重镇联袂召开。 …

第六届智能家居亚洲峰会暨精品展(Smart Home Asia 2022)将于10月在沪召开

智能家居作为物联网、云服务和人工智能技术的产业化应用&#xff0c;涉及计算机视听觉、生物特征识别、新型人机交互、智能决策控制等相关先进技术&#xff0c;受到国家政策的大力支持。基于广阔的市场空间、5G、IoT、AI等技术快速迭代、新基建的政策红利以及新消费形势的需求&…

2022-2028全球与中国智能家居设备市场现状及未来发展趋势

2021年全球智能家居设备市场销售额达到了 亿美元&#xff0c;预计2028年将达到 亿美元&#xff0c;年复合增长率&#xff08;CAGR&#xff09;为 %&#xff08;2022-2028&#xff09;。地区层面来看&#xff0c;中国市场在过去几年变化较快&#xff0c;2021年市场规模为 百万美…

国美在线“8.3男人节”来了 3C家电百货五折扫货就在今天

转眼进入8月&#xff0c;电商行业又展开了新的的角逐。据悉&#xff0c;国美在线将斥巨资打造最强8月最强的“8.3男人节”大促活动&#xff0c;男人节先锋战于7月28日正式开启。另外&#xff0c;还有一点值得注意&#xff0c;7月26日&#xff0c;国美在线与大润发飞牛网达成战略…

利基战略

利基战略&#xff08;Market-nicher strategy&#xff09;——企业全球化策略的新宠 <script type"text/javascript"> if (window.showTocToggle) { var tocShowText "显示"; var tocHideText "隐藏"; showTocToggle(); } </script&…
最新文章