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

Leetcode:518. 零钱兑换 II(C++)

目录

518. 零钱兑换 II

问题描述:

实现代码与解析:

动态规划(完全背包):

原理思路:

377. 组合总和 Ⅳ

问题描述:

实现代码与解析:

动态规划(完全背包):

原理思路:


518. 零钱兑换 II

问题描述:

        给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:amount = 10, coins = [10] 
输出:1

实现代码与解析:

动态规划(完全背包):

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

原理思路:

        和Leetcode:494. 目标和(C++)_Cosmoshhhyyy的博客-CSDN博客很像,只不过一个是一个数只能用一次,而本题可以用多次,也就是完全背包求组合数的问题,完全背包的代码可以看看

动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)_Cosmoshhhyyy的博客-CSDN博客_c++代码优化工具        两者结合一下就很好写出了,不再解释了,比较简单。

377. 组合总和 Ⅳ

问题描述:

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

实现代码与解析:

动态规划(完全背包):

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {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] && dp[j] < INT_MAX - dp[j - nums[i]]){dp[j] += dp[j - nums[i]];}             }}       return dp[target];}
};

原理思路:

        此题与上题相似,放在一次主要是注意这两题的差别,此题强调的是顺序,不同顺序也是一个结果,而上一题顺序无所谓,只算一总结果。

        先说结论吧,先遍历物品的话,就是上一题不用管顺序,先遍历背包的话,就是这题需要在意顺序。

        注意这个 if 的判断阿,因为我们先遍历背包了,int j = nums[i] 的逻辑就只能放在这里了。

if(j >= nums[i])
{dp[j] += dp[j - nums[i]];
}      

        因为有一组测试数据相加超过int范围,所以就多加了一个dp[j] < INT_MAX - dp[j - nums[i]]的判断,其余不变。

相关文章:

Leetcode:518. 零钱兑换 II(C++)

目录 518. 零钱兑换 II 问题描述&#xff1a; 实现代码与解析&#xff1a; 动态规划&#xff08;完全背包&#xff09;&#xff1a; 原理思路&#xff1a; 377. 组合总和 Ⅳ 问题描述&#xff1a; 实现代码与解析&#xff1a; 动态规划&#xff08;完全背包&#xff0…...

Java中类是什么

类(class)是构造对象的模板或蓝图。 我们可以将类想象成制作小甜饼的模具&#xff0c;将对象想象为小甜饼。由类构造(construct)对象的过程称为创建类的实例(instance)。 正如前面所看到的&#xff0c;用Java 编写的所有代码都位于某个类里面。 标准 Java 库提供了几千个类&a…...

C进阶:预处理

&#x1f916;本篇文章主要讲解预处理的知识&#xff0c;即使你是小白也可以看的懂&#xff0c;若你对预处理有所不解&#xff0c;确定不来看看吗&#xff1f;&#x1f63f; 目录 一.代码运行是的两种环境 二.翻译环境 三.预定义符号 四.#define 1.define 定义宏 2.带有…...

侯捷C++系统工程师

前言我相信对于每一个学习C的同学和从业者来说&#xff0c;台湾著名学者侯捷老师的C系列都是不可错过的好视频。侯捷老师在网上已有五门课&#xff0c;分别是&#xff1a;C面向对象开发、STL标准库与泛型编程、C新标准C1&14、C内存管理机制以及C Startup揭秘讲师介绍侯捷老…...

ReentrantReadWriteLock、StampedLock

ReentrantLock、ReentrantReadWriteLock、StampedLock 读写锁 一个资源可以被多个读线程访问&#xff0c;或者被一个写线程访问&#xff0c;但是不能同时存在读写线程。 小口诀&#xff1a;读写互斥&#xff0c;读读共享 锁的演变 无锁-----> 独占锁----->读写锁---…...

Mysql中的事务、锁、日志详解

一、事务 1.事务特性及保证事务特性的原理 原子性&#xff1a;当前事务的操作要么全部成功&#xff0c;要么全部失败。原子性由undo log实现&#xff0c;undo log记录了每次操作之前的数据版本&#xff0c;如果某一操作失败&#xff0c;可以根据undo log回滚到最初状态。一致…...

k8s笔记24--安装metrics-server及错误处理

k8s笔记24--安装metrics-server及错误处理1 介绍2 安装3 常见错误第一次错误 持续 Failed probe第二次错误 bad status code "403 Forbidden"4 说明1 介绍 最近一个同事在老版本的 k8s 上安装metrics-server&#xff0c;pod一直处于running 非就绪状态&#xff0c;经…...

【电商】订单系统--售后的简易流程与系统关系

用户进行了订单签收并不意味着终结&#xff0c;这只是一个新的开始&#xff0c;因为商品送达后可能会由于运输过程包装或商品有破损&#xff0c;商品本质量并非商品详情中所描述的那样等各种原因使用户进行退货或换货&#xff1b;还有一种场景是用户签收后发现有的商品漏发、少…...

低代码开发平台|生产管理-成本核算搭建指南

1、简介1.1、案例简介本文将介绍&#xff0c;如何搭建生产管理-成本核算。1.2、应用场景计算主生产及子生产计划的工序成本、领料成本&#xff0c;统计出总的生产成本金额。2、设置方法2.1、表单搭建1&#xff09;新建表单【商品信息】&#xff0c;字段设置如下&#xff1b;名称…...

Xshell 安装及使用方法

公网地址&#xff1a;47.XXX.XXX.229 私网地址&#xff1a;172.XXX.128.XXX 用户&#xff1a;root 密码&#xff1a;1234561,百度xshell&#xff0c;下载&#xff0c;安装Xshell 2&#xff0c;填写配置及使用方式 主机&#xff1a;47.XXX.XXX.229 用户&#xff1a;root 密码&a…...

【Axure教程】转盘抽奖原型模板

转盘抽奖是营销活动中很常用的一种方式&#xff0c;在线上我们也可以经常看到转盘抽奖的活动&#xff0c;所以今天作者就教大家在Axure中怎么制作一个转盘抽奖的原型模板。一、效果展示1、可以随机转动轮盘&#xff0c;轮盘停止时&#xff0c;指针对着的奖品高亮显示2、可以重复…...

量子比特大突破!原子薄材料成为“救世主”

&#xff08;图片来源&#xff1a;网络&#xff09;量子计算是一项极其复杂的技术&#xff0c;现阶段的一些挑战正严重阻碍着它的发展&#xff0c;尤其是量子比特的小型化和质量问题。IBM计划在2023年实现具有1121个超导量子比特的处理器。以目前的技术手段&#xff0c;要达到这…...

Swagger3 API接口文档规范课程(内含教学视频+源代码)

Swagger3 API接口文档规范课程&#xff08;内含教学视频源代码&#xff09; 教学视频源代码下载链接地址&#xff1a;https://download.csdn.net/download/weixin_46411355/87431932 目录Swagger3 API接口文档规范课程&#xff08;内含教学视频源代码&#xff09;教学视频源代…...

数据库的基本操作

查看数据库语法格式&#xff1a;SHOW {DATABASES | SCHEMAS}[LIKE pattern | WHERE expr]#查看全部数据库mysql> show databases; -------------------- | Database | -------------------- | information_schema | | mysql | | performance_schema …...

分享5个超好用的Vue.js库

开发人员最好的朋友和救星就是这些第三方库&#xff0c;无论是开发新手还是经验丰富的老手&#xff0c;我们都喜欢开源软件包。借助开源库加速Vue项目的开发进度是现代前端开发比较常见的方式&#xff0c;这几个 Vue.js库&#xff0c;建议尽早用上&#xff0c;加速你的项目开发…...

第四章.误差反向传播法—ReLU/Sigmoid/Affine/Softmax-with-Loss层的实现

第四章.误差反向传播法 4.2 ReLU/Sigmoid/Affine/Softmax-with-Loss层的实现 1.ReLU层 1).公式 2).导数&#xff1a; 3).计算图&#xff1a; 4).实现&#xff1a; class ReLU:def __init__(self):self.mask None# 正向传播def forward(self, x):self.mask (x < 0) # 输入…...

Python-第二天 Python基础语法

Python-第二天 Python基础语法一、 字面量1.1 常用的值类型1.1.1 字符串&#xff08;string&#xff09;二、注释2.1 注释的作用2.2 注释的分类三、变量3.1 什么是变量3.2 变量的特征四、数据类型4.1 数据类型4.2 type()语句4.3 type()语句的使用方式4.4 变量有类型吗&#xff…...

命令模式包含哪些主要角色?怎样实现命令?

命令模式包含以下主要角色&#xff1a;抽象命令类&#xff08;Command&#xff09;角色&#xff1a; 定义命令的接口&#xff0c;声明执行的方法。具体命令&#xff08;Concrete Command&#xff09;角色&#xff1a;具体的命令&#xff0c;实现命令接口&#xff1b;通常会持有…...

SpringCloud-Feign

Spring Cloud中集成Feign (只是笔记而已 其中有点命名啥的不对应&#xff0c;搜到了就划走吧) Feign--[feɪn]&#xff1a;Web 服务客户端&#xff0c;能够简化 HTTP 接口的调用。 没有Feign的之前服务提供者 package com.springcloudprovide.controller;import com.springclo…...

XCP实战系列介绍08-基于Vehicle Spy进行XCP测量的工程配置详解

本文框架 1.概述2. 工程配置步骤2.1 创建MEP工程2.1.1 添加A2L文件2.1.2 CAN收发ID配置2.2 MEP属性设置2.2.1 ECU属性设置2.2.2 MEP的Security设置2.3 DAQ设置2.3.1创建DAQ2.3.2 list中测量及标定量的添加和设置2.3.3 设置DAQ list中变量的event1.概述 在前面一篇文章《看了就…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...