Leetcode 377 组合总和 Ⅳ
题意理解:
给你一个由 不同 整数组成的数组
nums,和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。
这道题目和凑零钱是一样的,需要求使用指定元素(纸币),凑出target(指定金额)有多少种方式。
此处,元素是可以重复使用的,所以该问题是一个完全背包问题。
解题思路:
首先了解此题目是一个完全背包问题,所以遍历背包时正序,可以保证元素无限次使用。
其次,确定题目求得是有多少种方式,而不是重量或最大价值,该题目不是一个纯背包问题。
由于我们要求组成target得不同方式,1+2 和2+1 被看作是两种方式,所以这里求的是排列数,对于顺序有要求。
根据之前的总结:
求组合数:先物体后背包
求排列数,先背包后物体
所以我们选择第二种
1.动态规划解题
public int combinationSum4(int[] nums, int target) {if(nums.length<=0) return 0;int[] dp=new int[target+1];Arrays.fill(dp,0);dp[0]=1;for(int j=1;j<=target;j++){for(int i=0;i<nums.length;i++){if(nums[i]<=j){dp[j]+=dp[j-nums[i]];}}}return dp[target];}
2.分析
时间复杂度:O(n^2)
空间复杂度:O(n)
相关文章:
Leetcode 377 组合总和 Ⅳ
题意理解: 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 这道题目和凑零钱是一样的,需要求使用指定元素(纸币…...
CleanMyMacX4.14.6如何清理mac垃圾内存
一直以来,苹果电脑的运行流畅度都很好,但是垃圾内存多了磁盘空间慢慢变少,还是会造成卡顿的。这篇文章就告诉大家电脑如何清理垃圾内存,电脑如何清理磁盘空间。 一、电脑如何清理垃圾内存 垃圾内存指的是各种缓存文件和系统垃圾…...
Java 学习和实践笔记(1)
2024年,决定好好学习计算机语言Java. B站上选了这个课程:【整整300集】浙大大佬160小时讲完的Java教程(学习路线Java笔记)零基础,就从今天开始学吧。 在这些语言中,C语言是最基础的语言,绝大多…...
【自然语言处理-工具篇】spaCy<1>--介绍及安装指南
目录 前言 安装指南 pip conda spaCy升级 总结 前言 spaCy是一个开源的自然语言处理库,用于处理和分析文本数据。它提供了许多功能,包括分词、词性标注...
LeetCode树总结
144. 二叉树的前序遍历 递归写法很简单,不再赘述。迭代写法需要用到一个栈,因为是根->左子树->右子树的顺序进行遍历,所以弹出当前结点后要先入栈右儿子,再入栈左儿子。 /*** Definition for a binary tree n…...
AI专题:冬渐去、春将来,待看,AI 开花,数据挂果,可控链潮起
今天分享的是AI 系列深度研究报告:《AI专题:冬渐去、春将来,待看,AI 开花,数据挂果,可控链潮起》。 (报告出品方:AVIC) 报告共计:36页 行业概览:2023年呈稳…...
Netty源码系列 之 EventLoop run()方法 源码
EventLoop[实现类为NioEventLoop,我们研究NioEventLoop即可] EventLoop是一个单线程的线程池 核心作用:处理执行IO操作(accept,read,write事件),普通任务,定时任务 EventLoop封装…...
ChatGPT 4.0 升级指南, ChatGPT Plus(GPT 4.0) 有何优势?
1.ChatGPT 是什么? ChatGPT 是由 OpenAI 开发的一种基于人工智能的聊天机器人,它基于强大的语言处理模型 GPT(Generative Pre-trained Transformer)构建。它能够理解人类语言,可以为我们解决实际的问题。 ChatGPT 4.…...
springboot157基于springboot的线上辅导班系统的开发与设计
简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计,课程设计参考与学习用途。仅供学习参考, 不得用于商业或者非法用途,否则,一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…...
【机器学习】机器学习简单入门
🎈个人主页:甜美的江 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:matplotlib 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进…...
考研数据结构笔记(1)
数据结构(1) 数据结构在学什么?数据结构的基本概念基本概念三要素逻辑结构集合线性结构树形结构图结构 物理结构(存储结构)顺序存储链式存储索引存储散列存储重点 数据的运算 算法的基本概念什么是算法算法的五个特性有…...
【深度学习理论】持续更新
文章目录 1.统计学习理论 1.统计学习理论 统计学习理论,一款适合零成本搞深度学习的大冤种的方向 从人类学习到机器学习的对比(学习的过程分为归纳和演绎 ),引出泛化和过拟合的概念。 如何表示归纳的函数规律呢?以监督…...
npm ERR! reason: certificate has expired(淘宝镜像过期)
npm ERR! request to https://registry.npm.taobao.org/yauzl/-/yauzl-2.4.1.tgz failed, reason: certificate has expired 今天在执行npm install命令时,报错百度了下是淘宝证书过期原因 解决方法一 执行下面两个命令再进行npm install即可 npm cache clean --…...
“极简壁纸“爬虫JS逆向·实战
文章目录 声明目标分析确定目标目标检索 代码补全完整代码 爬虫逻辑完整代码 运行结果 声明 本教程只用于交流学习,不可用于商业用途,不可对目标网站进行破坏性请求,请遵守相关法律法规。 目标分析 确定目标 获取图片下载链接 目标检索…...
Django通过Json配置文件分配多个定时任务
def load_config():with open("rule.json", rb)as f:config json.load(f)return configdef job(task_name, config, time_interval):# ... 通过task_name判断进行操作if task_name get_data_times:passdef main():config load_config()for task_name, task_value…...
C++ 搜索二叉树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回 要删除的结点可能分下面四种情况: a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中…...
构建中国人自己的私人GPT—支持中文
上一篇已经讲解了如何构建自己的私人GPT,这一篇主要讲如何让GPT支持中文。 privateGPT 本地部署目前只支持基于llama.cpp 的 gguf格式模型,GGUF 是 llama.cpp 团队于 2023 年 8 月 21 日推出的一种新格式。它是 GGML 的替代品,llama.cpp 不再…...
elementui 回到顶部报错
<template>Scroll down to see the bottom-right button.<el-backtop target".page-component__scroll .el-scrollbar__wrap"></el-backtop> </template> 使用element的Backtop 回到顶部组件的伙伴们,把官网代码复制到页面使用时…...
go-carbon v2.3.8 发布,轻量级、语义化、对开发者友好的 golang 时间处理库
carbon 是一个轻量级、语义化、对开发者友好的 golang 时间处理库,支持链式调用。 目前已被 awesome-go 收录,如果您觉得不错,请给个 star 吧 github.com/golang-module/carbon gitee.com/golang-module/carbon 安装使用 Golang 版本大于…...
【详解】斗地主随机发牌项目
目录 前言: 1.初始化牌 2.洗牌 3.揭牌 总代码: Card类: CardGame类: Main类: 结语: 前言: 斗地主是全国范围内的一种桌面游戏,本节我们来实现一下斗地主中的简单初始化牌、…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
