​LeetCode解法汇总377. 组合总和 Ⅳ

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:. - 力扣(LeetCode)


描述:

动态规划。dp[i]代表target为i时的类型数量。

那么遍历nums数组,如果dp[i-nums[i]]>0,则dp[i]+=dp[i-nums[i]]即可。

解题思路:

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

代码:

class Solution {
public:
    int combinationSum4(vector<int> &nums, int target)
    {
        // sort(nums.begin(), nums.end());
        // int index = 0;
        vector<long long> dp(target + 1, 0);
        for (int i = 1; i < target + 1; i++)
        {
            for (int num : nums)
            {
                int abs = i - num;
                if (abs < 0)
                {
                    continue;
                }
                if (abs == 0)
                {
                    dp[i] += 1;
                    continue;
                }
                if (num <= i && dp[i - num] < INT_MAX - dp[i])
                {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

3i平台体验性能加持,13600KF+B760M+撼与科技A770 TITAN装机体验

在2022年&#xff0c;intel重启显卡线&#xff0c;带来了多款性价比十分不错的显卡。而近段时间&#xff0c;又有传言说intel第二代产品e即将面世&#xff0c;甚至已经有数款Battlemage GPU曝光&#xff0c;让不少intel忠实粉丝直呼期待&#xff0c;或许在今年年底&#xff0c;…

【新知实验室 - TRTC 实践】音视频互动 Demo、即时通信 IM 服务搭建

一、TRTC 初识 TRTC 是什么 TRTC&#xff08;Tencent RTC&#xff09;腾讯实时音视频&#xff0c;源自于 QQ 音视频团队&#xff0c;是基于 QQ 音视频多年来的音视频技术积累&#xff0c;位于腾讯云的 RTC 云服务。TRTC 支持腾讯会议、企业微信直播、微信视频号、腾讯云课堂、…

AI大模型探索之路-实战篇2:基于CVP架构-企业级知识库实战落地

目录 前言 一、概述 二、本地知识库需求分析 1. 知识库场景分析 2. 知识库应用特点 3. 知识库核心功能 三、本地知识库架构设计 1. RAG架构分析 2. 大模型方案选型 3. 应用技术架构选型 4. 向量数据库选型 5. 模型选型 三、本地知识库RAG评估 四、本地知识库代码落地 1. 文件…

leetcode最大间距(桶排序+Python)

虽然直接排完序&#xff0c;再求最大差值更快&#xff0c;这里我们还是学一下桶排序。 桶排序主要维护一个bucket&#xff0c;初始bucket【i】 0&#xff0c;遍历nums&#xff0c;当i存在时&#xff0c;令bucket【i】 1&#xff0c;表示存在。遍历完nums&#xff0c;bucket中有…

【点云语义分割】弱监督点云语义分割-双教师指导的对比学习

Weakly Supervised Learning for Point Cloud Semantic Segmentation With Dual Teacher 摘要&#xff1a; 为了增强特征学习能力&#xff0c;我们在这项工作中引入了双教师指导的对比学习框架&#xff0c;用于弱监督点云语义分割。双教师框架可以减少子网络耦合&#xff0c;促…

Java web应用性能分析之服务端慢[网络慢]

Java web应用性能分析之服务端慢&#xff0c;如果是网络原因引起的服务端慢&#xff0c;经常会被忽略&#xff0c;很多时候我们第一时间不会去排查网络原因。出现这种情况也很正常&#xff0c;因为应用的外部网络都是超100M的大宽带服务器&#xff0c;而内部则是千兆网卡或者万…

SpringCloud 与 Dubbo 的区别详解

一、Spring Cloud 和 Dubbo 的概述 1.1 SpringCloud 简介 SpringCloud 是一个用于构建云原生应用的框架集合&#xff0c;它为开发者提供了一套完整的工具链&#xff0c;用于快速搭建分布式系统。SpringCloud 基于 SpringBoot 开发&#xff0c;具有如下特点&#xff1a; 提供…

mysql常见语法操作笔记

1. 数据库的基本操作 1.1. MYSQL登录与退出 D:\phpstudy_pro\Extensions\MySQL5.7.26\bin 输入 mysql -uroot -proot -h127.0.0.1 退出的三种方法 mysql > exit; mysql > quit; mysql > \q; 1.2. MYSQL数据库的一些解释 注意&#xff1a;数据库就相当于文件夹 …

类和对象(2)——封装(封装的概念、包、staic)

前言 面向对象程序三大特性&#xff1a;封装、继承、多态。而类和对象阶段&#xff0c;主要研究的就是封装特性。何为封装呢&#xff1f;简单来说就是套壳屏蔽细节。 一、什么是封装 1.1 概念 将数据和操作数据的方法进行有机结合&#xff0c;隐藏对象的属性和实现细节&…

CXL论文阅读笔记整理(持续更新)

CXL 介绍 An Introduction to the Compute Express LinkTM (CXLTM) Interconnect arXiv Paper 对CXL技术进行介绍&#xff0c;包括CXL 1.0、CXL 2.0、CXL 3.0&#xff0c;对各规范的提升做介绍。整理了现有的CXL实现方法&#xff0c;延迟测试结果&#xff0c;对未来发展进行…

三分钟带你读懂面向对象的三大特征:封装,继承,多态

很多小伙伴在学面向对象的时候觉得非常抽象&#xff0c;尤其是对于面向对象的三大特征&#xff1a;封装&#xff0c;继承&#xff0c;多态不理解&#xff0c;那这期文章呢&#xff0c;九九就给大家安排&#xff0c;三分种带你迅速掌握封装&#xff0c;继承&#xff0c;多态。 …

17.基础乐理-调式、自然大调式(C大调、D大调。。。)

调式&#xff1a; 若干个音&#xff0c;按照某种规则排列起来&#xff0c;就是调式&#xff0c;调式是一个非常大&#xff0c;非常抽象的概念&#xff0c;调式这两个字是一个统称&#xff0c;当明确了 若干个音 到底有几个音&#xff0c;某种规则到底是什么规则之后&#xff0c…

刚拿到的《HarmonyOS应用开发者高级认证》,全网整理的题目,将近300题,100%通过

刚拿到《HarmonyOS应用开发者高级认证》&#xff0c;现在把题目和答案分享一下&#xff0c;这些题目是我根据其他网站整理的&#xff0c;宁滥勿缺&#xff0c;有个别题目是重复的&#xff0c;抽半天时间看一下&#xff0c;应该是稳过的。当然建议还是先跟着文档学一下鸿蒙或者看…

【UE5.1】使用MySQL and MariaDB Integration插件——(4)修改、插入、删除数据

目录 效果 步骤 一、修改 二、插入、删除 在上一篇博客&#xff08;【UE5.1】使用MySQL and MariaDB Integration插件——&#xff08;3&#xff09;表格形式显示数据&#xff09;基础上继续实现修改、插入和删除数据库数据的功能 效果 修改数据&#xff1a; 插入数据&…

【YOLO系列PR、F1绘图】更改v5、v7、v8(附v8训练、验证方式),实现调用val.py或者test.py后生成pr.csv,然后再整合绘制到一张图上(使用matplotlib绘制)

目录 1. 前提 效果图2. 更改步骤2.1 得到PR_curve.csv和F1_curve.csv2.1.1 YOLOv7的更改2.1.1.1 得到PR_curve.csv2.2.1.2 得到F1_curve.csv 2.1.2 YOLOv5的更改&#xff08;v6.1版本&#xff09;2.1.3 YOLOv8的更改&#xff08;附训练、验证方式&#xff09; 2.2 绘制PR曲线 …

在CSDN创作了6个月,我收获了什么?文末送书~

作者主页&#xff1a;阿玥的小东东主页&#xff01; 正在学习&#xff1a;python和C/C 期待大家的关注哦 目录 一次很好的机会&#xff0c;让我开始了CSDN之旅 首先来看看我的几位领路人 创作动力 1W粉丝 在CSDN我收获了什么&#xff1f; 很高的展现量 认证创作者身份 社…

Linux 网络操作命令FTP

FTP命令 引言 文件传输协议&#xff08;FTP&#xff09;是一种用于在网络上进行文件传输的协议。在Linux系统中&#xff0c;FTP可以作为一个非常有用的工具来上传、下载和管理文件。本文将介绍如何在Linux系统中安装FTP服务器&#xff0c;以及如何使用FTP客户端进行文件传输。…

RabbitMQ进阶学习

在之前的练习作业中&#xff0c;我们改造了余额支付功能&#xff0c;在支付成功后利用RabbitMQ通知交易服务&#xff0c;更新业务订单状态为已支付。 但是大家思考一下&#xff0c;如果这里MQ通知失败&#xff0c;支付服务中支付流水显示支付成功&#xff0c;而交易服务中的订…

充电器进阶,原边恒流,单片机控制小电流(预充电)的方案

前言 很多充电器&#xff0c;为了能控制电流输出&#xff0c;也就是充电时需要有小电流、大电流的情况&#xff0c;都会用副边及单片机进行控制&#xff0c;但因为是副边控制&#xff0c;需要一个比较器、一个二极管、若干电阻、若干电容&#xff0c;整体BOM成本可能多了三毛钱…

VUE 项目 自动按需导入

你是否有这样的苦恼&#xff0c;每个.vue都需要导入所需的vue各个方法 unplugin-auto-import 库 Vite、Webpack和Rollup的按需自动导入API 本章提供Vite、Webpack中使用说明 1. 安装 npm i -D unplugin-auto-import 2. config.js 配置文件内追加配置 2.1 Vite // vite.conf…