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

Leetcode DAY 44: 完全背包 and 零钱兑换 II and 组合总和 Ⅳ

  • 完全背包

  • 518. 零钱兑换 II

·!!!程序未通过原因:

1、dp数组的初始化没考虑清楚

2、组合问题   dp数组的更新没考虑清楚

 修改后:

class Solution {
public:int change(int amount, vector<int>& coins) {// dp[j]表示装满容量为j的背包一共有多少种方法vector<int> dp(amount + 1, 0);int n = coins.size();dp[0] = 1;for(int i = 0; i < n; i++){for(int j = coins[i]; j <= amount; j++){//组合数问题dp[j] += dp[j - coins[i]];}}return dp[amount];}
};
  • 377. 组合总和 Ⅳ

注意!!!

如果求组合数就是外层for循环遍历物品,内层for遍历背包。

如果求排列数就是外层for遍历背包,内层for循环遍历物品。

先遍历物品的时候相当于是先把这个物品放进去了然后再看其他的能不能放进去,所以不会出现逆序,

先遍历背包相当于是用每个大小的背包看看把每一个物品都放进去一次再看别的物品能不能放进去,所以可以有逆序

程序未通过原因:

1、未考虑 j >= nums[i] 

2、C++测试用例有两个数相加超过int的数据,所以需要在if里加上dp[i] < INT_MAX - dp[i - num]

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {//dp[j] 表示 装满背包为j的 排列数vector<int> dp(target + 1, 0);dp[0] = 1;// 先遍历背包 再遍历物品for(int j = 0; j <= target; j++){for(int i = 0; i < nums.size(); i++){if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) {dp[j] += dp[j - nums[i]];}}}return dp[target];}
};

相关文章:

Leetcode DAY 44: 完全背包 and 零钱兑换 II and 组合总和 Ⅳ

完全背包518. 零钱兑换 II&#xff01;&#xff01;&#xff01;程序未通过原因&#xff1a; 1、dp数组的初始化没考虑清楚 2、组合问题 dp数组的更新没考虑清楚 修改后&#xff1a; class Solution { public:int change(int amount, vector<int>& coins) {// dp[j…...

谷歌搜索留痕的技术公式【2023年新版】

本文主要分享谷歌搜索留痕的技术公式&#xff0c;让你更简单的去学习谷歌留痕的技术原理 本文由光算创作&#xff0c;有可能会被修改和剽窃&#xff0c;我们佛系对待这样的行为吧。 谷歌搜索留痕的技术公式是什么&#xff1f; 答案是&#xff1a;需要做排名的关键词海量能搜…...

2023财年Q4业绩继续下滑,ChatGPT能驱动英伟达重回巅峰吗?

近年来&#xff0c;全球科创风口不断变换&#xff0c;虚拟货币、元宇宙等轮番登场&#xff0c;不少企业匆忙上台又很快谢幕&#xff0c;但在此期间&#xff0c;有些企业扮演淘金潮中“卖水人”的角色&#xff0c;却也能够见证历史且屹立不倒。不过&#xff0c;这并不意味着其可…...

博客管理系统--项目说明

项目体验地址&#xff08;账号&#xff1a;123&#xff0c;密码&#xff1a;123&#xff09;http://120.53.20.213:8080/blog_system/login.html项目码云Gitee地址&#xff1a;https://gitee.com/GoodManSS/project/tree/master/blog_system&#xff08;一&#xff09;准备工作…...

一文带你了解MySQL的Server层和引擎层是如何交互的?

对于很多开发小伙伴来说&#xff0c;每天写SQL是必不可少的一项工作。 那不知道大家有没有深入了解过&#xff0c;当我们的一条SQL命令被执行时&#xff0c;MySQL是如何把数据从硬盘/内存中查出来并展示到用户面前的呢&#xff1f; 其实&#xff0c;MySQL也没有大家想象的那么…...

CVNLP 常用数据集语料库资源汇总

​ 深度学习常用数据集汇总CVClassificationNLPSentiment AnalysisText ClassificationDialogue Generation其他AudioMulti-ModalClassificationSearch & MatchingImage CaptioningVisualQATri-Modal其他CV ghcnclimate_sphereModelNet40Shrec17 data labelcosmo Spherica…...

lisp 表达式求值规则

lisp 表达式求值规则 一个要求值的 lisp 对象被称为lisp表达式&#xff08;form&#xff09;。 lisp 表达式分三种 1. 自求值表达式。前面说过数字、字符串、向量都是自求值表达式。还有两个特殊的符号 t 和 nil 也可以看成是自求值表达式。 2. 符号表达式。符号的求值…...

Sophos Firewall OS (SFOS) 19.5 MR1 - 同步下一代防火墙

Sophos Firewall OS (SFOS) 19.5 MR1 - 同步下一代防火墙 请访问原文链接&#xff1a;https://sysin.org/blog/sfos-19-5/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;www.sysin.org Sophos Firewall v19.5 现已推出 Sophos Firewall…...

为什么很多人转行IT考虑后端开发Java?

顺应互联网时代发展的选择 在计算机广泛运用于社会的各个角落的今天&#xff0c;选择学习一门计算机语言真的很不错&#xff0c;它会让你的生活从此与众不同。软件渗透到组织的运营和管理的后台之中&#xff0c;形成了组织运营支撑平台。这种形态是传统软件的重要应用场景。在…...

WebDAV之π-Disk派盘+Cloud Player

Cloud Player 支持WebDAV方式连接π-Disk派盘。 推荐一款云媒体播放器是存储在常见云平台中的内容的通用播放器。 Cloud Player云媒体播放器是存储在常见云平台中的内容的通用播放器,无需将其下载到设备。支持以下云平台:Google Drive、DropBox、One Drive、WebDav等。此外,…...

Python-datetime、time包常用功能汇总

目录基础知识时间格式有哪些&#xff1f;Python中的时间格式化时间戳datetimedatedatetimetimedeltatime常用获取今天凌晨字符串&#xff1f;将一个时间格式的字符串转为时间戳将一个时间戳转为指定格式的字符串全部代码参考基础知识 时间格式有哪些&#xff1f; 「格林威治标…...

Spring MVC 源码- HandlerAdapter 组件(四)之 HandlerMethodReturnValueHandler

HandlerAdapter 组件HandlerAdapter 组件&#xff0c;处理器的适配器。因为处理器 handler 的类型是 Object 类型&#xff0c;需要有一个调用者来实现 handler 是怎么被执行。Spring 中的处理器的实现多变&#xff0c;比如用户的处理器可以实现 Controller 接口或者 HttpReques…...

2023面试必备:web自动化测试POM设计模式详解

1.背景 为UI页面写自动化测试用例时&#xff08;如&#xff1a;web自动化、app自动化&#xff09;&#xff0c;使用普通的线性代码&#xff0c;测试用例中会存在大量的元素定位及操作细节&#xff0c;当UI界面变化时&#xff0c;测试用例也要跟着变化&#xff0c;在自动化测试…...

【人工智能 AI】Robotic Process Automation (RPA) 机器人流程自动化 (RPA)

目录 ROBOTIC PROCESS AUTOMATION SERVICES机器人流程自动化服务 What is RPA? 什么是机器人流程自动化?...

ubuntu/linux系统知识(37)systemd管理临时文件的方法systemd-tmpfiles

1、systemd-tmpfiles Linux产生大量的临时文件和目录&#xff0c;例如/tmp、/run 。systemd提供了一个结构化的可配置方法来管理临时文件和目录&#xff0c;即systemd-tmpfiles工具和配套的几个服务&#xff0c;以实现创建、删除和管理临时文件。 systemd创建了几个调用syste…...

云计算专业和计算机专业哪个好就业?

云计算专业其实也是属于计算机类专业呢&#xff0c;他包括了计算机硬件设备、计算机网络、磁盘柜、操作系统、中间件、数据库、服务器/虚拟机、应用软件开发等技术内容&#xff0c;云计算技术是以IT服务的形式面向用户的&#xff1b;所以云计算不是一门技术&#xff0c;而是众多…...

electron sha512 checksum mismatch

sha512 checksum mismatch错误 此错误常常发生在electron检查更新时&#xff0c;导致检查更新失败。 自动更新使用的模块 electron-updater or electron-differential-updater win下electron-builder打包 使用electron-builder打包之后&#xff0c;进行版本增量更新遇到的…...

使用Chemistry Development Kit (CDK) 来进行化学SMILES子结构匹配

摘要 SMILES是一种用于描述化合物结构的字符串表示法&#xff0c;其中子结构搜索是在大规模化合物数据库中查找特定的结构。然而&#xff0c;这种搜索方法存在一个误解&#xff0c;即将化合物的子结构视为一个独立的实体进行搜索&#xff0c;而忽略了它们在更大的化合物中的上…...

CMake模块的使用和自定义模块

CMake模块的使用和自定义模块一、前言二、使用Find模块2.1、准备工作2.2、添加头文件路径和库文件2.3、< name >_FOUND 来控制工程特性三、编写自定义的Find模块3.1、 准备工作3.2、cmake 模块3.3、使用自定义的FindHELLO 模块构建工程3.4、如果没有找到hello library四、…...

jvm调优参数配置

在JVM启动参数中&#xff0c;可以设置跟内存、垃圾回收相关的一些参数设置&#xff0c;默认情况不做任何设置JVM会工作的很好&#xff0c;但对一些配置很好的Server和具体的应用必须仔细调优才能获得最佳性能。通过设置我们希望达到一些目标&#xff1a; GC的时间足够的小 GC的…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

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

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

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...