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

518. Coin Change II

news 来源：原创 2025/9/18 15:21:45

这是完全背包问题。

由于求的是组合数，所以外层循环只能是对硬币遍历，内层循环只能是对总金额的遍历。

另外，虽然题目数据保证结果符合 32 位带符号整数。但是第28个测试用例，dp[j]+dp[j-conis[i]]中间结果会整数溢出，需要特别处理这种情况。

第一版代码

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();//dp[j]表示从coins中任选若干个硬币，被选中的硬币的价值总和等于j的选法数量vector<int> dp(amount+1,0);//除了dp[0]外都初始化为0，表示没有硬币可选的时候没有办法选到大于0的价值总和（选法为0）dp[0] = 1;//表示没有硬币可选的时候，选择0个硬币，选到的硬币价值总和等于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];}
};

可以看到第28个测试用例，会溢出：

第二版代码

把数据类型改成long long 仍然会溢出：

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();//dp[j]表示从coins中任选若干个硬币，被选中的硬币的价值总和等于j的选法数量vector<long long> dp(amount+1,0);//除了dp[0]外都初始化为0，表示没有硬币可选的时候没有办法选到大于0的价值总和（选法为0）dp[0] = 1;//表示没有硬币可选的时候，选择0个硬币，选到的硬币价值总和等于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];}
};

结果：

第三版代码

中间结果溢出，则直接返回0。这样处理，可以通过用例，但中间结果溢出，是不是代表dp[amount]一定是0，这是个有待思考的问题？但从做题角度来说，这样刚好可以通过。

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();//dp[j]表示从coins中任选若干个硬币，被选中的硬币的价值总和等于j的选法数量vector<int> dp(amount+1,0);//除了dp[0]外都初始化为0，表示没有硬币可选的时候没有办法选到大于0的价值总和（选法为0）dp[0] = 1;//表示没有硬币可选的时候，选择0个硬币，选到的硬币价值总和等于0的选法有1种for(int i = 0;i < n;i++){for(int j = coins[i];j <= amount;j++){if((long)dp[j] + (long)dp[j-coins[i]] > std::numeric_limits<int>::max())return 0;dp[j] = dp[j] + dp[j-coins[i]];}}return dp[amount];}
};

第四版代码

把数据类型改成double试试看，发现可以通过

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();//dp[j]表示从coins中任选若干个硬币，被选中的硬币的价值总和等于j的选法数量vector<double> dp(amount+1,0);//除了dp[0]外都初始化为0，表示没有硬币可选的时候没有办法选到大于0的价值总和（选法为0）dp[0] = 1;//表示没有硬币可选的时候，选择0个硬币，选到的硬币价值总和等于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];}
};

第28个测试用例的coins是

{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,244,246,248,250,252,254,256,258,260,262,264,266,268,270,272,274,276,278,280,282,284,286,288,290,292,294,296,298,300,302,304,306,308,310,312,314,316,318,320,322,324,326,328,330,332,334,336,338,340,342,344,346,348,350,352,354,356,358,360,362,364,366,368,370,372,374,376,378,380,382,384,386,388,390,392,394,396,398,400,402,404,406,408,410,412,414,416,418,420,422,424,426,428,430,432,434,436,438,440,442,444,446,448,450,452,454,456,458,460,462,464,466,468,470,472,474,476,478,480,482,484,486,488,490,492,494,496,498,500,502,504,506,508,510,512,514,516,518,520,522,524,526,528,530,532,534,536,538,540,542,544,546,548,550,552,554,556,558,560,562,564,566,568,570,572,574,576,578,580,582,584,586,588,780,936,1170,1560,2340,4680}

第五版代码

采用leetcode官方题解的办法。这种办法相比于第三版代码，逻辑上的正确性更好理解。

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();//valid[j]表示是否能够从coins中选择若干个硬币使得所选硬币的金额总和等于jvector<bool> valid(amount+1,false);valid[0] = true;for(int i = 0;i < n;i++){for(int j = coins[i];j <= amount;j++){valid[j] = valid[j] || valid[j-coins[i]];}}if(!valid[amount])return 0;//dp[j]表示从coins中任选若干个硬币，被选中的硬币的价值总和等于j的选法数量vector<int> dp(amount+1,0);//除了dp[0]外都初始化为0，表示没有硬币可选的时候没有办法选到大于0的价值总和（选法为0）dp[0] = 1;//表示没有硬币可选的时候，选择0个硬币，选到的硬币价值总和等于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];}
};

518. Coin Change II

这是完全背包问题。由于求的是组合数，所以外层循环只能是对硬币遍历，内层循环只能是对总金额的遍历。另外，虽然题目数据保证结果符合 32 位带符号整数。但是第28个测试用例，dp[j]dp[j-conis[i]]中间结果会整数溢出&#xff0c…...

编程日记 2025/9/18 15:21:45

GPIO子系统与Pinctrl子系统的交互

我们前面呢，已经讲过GPIO子系统的数据结构以及他的设备树信息是怎么转换成我们的C代码存储在结构体里面了，我们知道，如果想去使用一个GPIO，避免不了得把这个引脚复用成GPIO功能，那么就避不开Pinctrl子系统，…...

编程日记 2025/9/13 8:49:05

DeepSeek实用操作及行业应用系列2

DeepSeek的本地化部署与AI通识教育之未来 DeepSeek之火，可以燎原面向审计行业DeepSeek大模型操作指南v1.0 DeepSeek提示词设计、幻觉避免与应用（大数据百家讲坛） DeepSeek 搞钱教程（0基础入门） DeepSeek基础知识…...

编程日记 2025/8/25 21:20:50

面向数据库场景的大模型交互微调数据集

关键要点研究表明，面向数据库场景的大模型交互微调数据集通常包括数据库模式、自然语言查询和对应的SQL查询。证据倾向于认为，数据集应以JSON格式组织，覆盖多种查询类型，并确保高质量和多样性。对于自定义数据库，建议…...

编程日记 2025/9/8 11:27:24

解锁ChatGPT-4o文生图潜力：精选提示词收集整理更新中

示例一：按元素和描述要求生成图片示例二：“吉卜力”风格示例三：3D Q版风格示例四：生成指定布局和主题图片具体的提示词参考，陆续更新中：https://blog.luler.top/d/25...

编程日记 2025/8/18 0:54:39

WHAT - React 进一步学习推荐

书籍 adevnadia 的《Advanced React》TejasKumar_ 的《Fluent React》addyosmani 和 djirdehh 的《Building Large Scale Web Apps》面试准备 reactjs-interview-questions 文章：最佳实践如果你想了解最佳实践并学习技巧，请务必关注以下专家&…...

编程日记 2025/9/10 1:05:35

有关串口的知识点

轻微了解一般都是前这俩01 Ren1才能接受开局T1 R1要给0 所以就是0x50的起手终端服务是接受的 ———————————————————————————— 进入实际引用使用的时候1 初始化 2要给个500ms的延时函数即可...

编程日记 2025/9/18 15:17:41

无线插卡话机如何接入呼叫中心系统？

一、接入原理与技术架构无线插卡话机通过内置SIM卡模块（支持GSM/CDMA/4G/5G等网络制式），将移动网络信号转化为语音通信信号，再通过SIP协议或专用网关与呼叫中心系统对接。其核心流程包括： 1、网络信号…...

编程日记 2025/9/18 15:18:28

prometheus有几种数据类型

Prometheus 数据类型主要有以下四种： Counter（计数器）： 单调递增的数值，表示某个事件发生的次数。计数器的值只会增加，除非被重置为0（例如在系统重启时）。示例：HTTP 请求…...

编程日记 2025/9/18 15:17:02

C++设计模式+异常处理

#include <iostream> #include <cstring> #include <cstdlib> #include <unistd.h> #include <sstream> #include <vector> #include <memory> #include <stdexcept> // 包含异常类using namespace std;// 该作业要求各位写一…...

编程日记 2025/9/18 15:18:28

字符串替换（模拟）神奇数（数学）DNA序列（固定长度的滑动窗口）

⭐️个人主页：小羊 ⭐️所属专栏：每日两三题很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~ 目录字符串替换 （模拟）神奇数 （数学）DNA序列 （固定长度的滑动窗口&am…...

编程日记 2025/9/12 0:58:33

echarts地图详解

获取地图坐标json数据 <template><div id"china-map" style"width:500px;height:500px"></div> </template> <script>import * as echarts from echarts;// 坐标jsonimport chinaJson from "/assets/china.json" …...

编程日记 2025/9/12 0:58:29

Redis 哨兵模式：告别手动故障转移！

目录前言一、 Redis哨兵模式是啥？🤔二、为什么需要哨兵模式？🤷‍♀️三、哨兵模式的原理是什么？🤝1. 监控（Monitoring）2. 信息共享与客观下线判断3. 哨兵领导者选举4. 故障转移5.…...

编程日记 2025/9/12 9:28:14

地理数据输出

为了便于数据共享和交换，可以将地理数据库中的要素数据输出为Shapefiles或者Coverage，将相应的属性表输出为Info或者dBase格式的数据文件。 1.输出为 Shapefile (1)在AreCatalog目录树或者内容栏中，右键点击需要输出的地理要素类，…...

编程日记 2025/9/16 8:07:15

springboot + security + redis + jwt 实现验证登录上

前言： 通过实践而发现真理，又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识，又从理性认识而能动地指导革命实践，改造主观世界和客观世界。实践、认识、再实践、再认识，这种形式，循环往…...

编程日记 2025/9/9 2:21:14

SomeIP通讯机制

在SOME/IP协议中，通讯方式主要围绕服务的交互模式进行的设计，核心机制包括Event（时间）、Method（方法）以及其变种Fire-and-Forget（FF）。以下是SOME/IP中所有通信方式的总结&#xff1…...

编程日记 2025/9/11 7:49:47

线代第三课：n阶行列式

引言行标取自然排列不同行不同列的3个元素相乘列标取排列的所有可能列标排列的逆序数的奇偶性决定符号，- n阶行列式第一种：按行展开 (1) 行标取自然排列 (2) 列标取排列的所有可能 （PS：可以理解为随意取） (3) 从…...

编程日记 2025/9/14 5:58:10

人工智能在高中教育中的应用现状剖析与挑战应对

第一章：绪论 1.1 研究背景与意义随着全球化的加速和科技的飞速发展，高中教育在培养未来社会所需人才方面的重要性日益凸显。高中阶段是学生知识体系构建和思维能力发展的关键时期，然而，当前高中教育面临着诸多挑战，…...

编程日记 2025/9/9 12:00:26

如何在powerbi使用自定义SQL

我们在刚使用到powerbi的时候发现当直接连接到数据库的时候我们只能使用数据库中已存在的表，我们没有办法使用自定义SQL来准备数据，这给我们的开发造成很大的困扰；我目前使用的是vertica数据库，首先我们需要在本地有vertica的驱动…...

编程日记 2025/9/13 8:56:51

边缘计算盒子是什么？

边缘计算盒子是一种小型的硬件设备，通常集成了处理器、存储器和网络接口等关键组件，具备一定的计算能力和存储资源，并能够连接到网络。它与传统的云计算不同，数据处理和分析直接在设备本地完成，而不是上传到云端&#…...

编程日记 2025/9/17 10:35:20

【C++面向对象】封装(上)：探寻构造函数的幽微之境

每文一诗 💪🏼 我本将心向明月，奈何明月照沟渠 —— 元/高明《琵琶记》译文：我本是以真诚的心来对待你，就像明月一样纯洁无瑕；然而，你却像沟渠里的污水一样，对这份心意无动于衷&a…...

编程日记 2025/9/15 21:42:34

物联网|无人自助台球厅源码|哪些框架支持多设备连接？

在无人自助台球厅的智能化管理中，物联网（IoT）技术是核心支撑。如何实现不同设备（如智能门锁、环境传感器、支付终端、灯光控制系统等）的高效连接与协同工作，是系统开发的关键挑战。本文将带大家探讨支持多设…...

编程日记 2025/9/9 18:42:35

单旋翼无人机(直升机)和四旋翼无人机优势对比

以下是无人机直升机（单旋翼无人机）与四旋翼无人机的优势对比分析，分场景阐述两者的核心差异： ‌一、无人机直升机（单旋翼无人机）的优势‌ ‌1. 高能量效率，长续航‌ ‌动力设计‌：单…...

编程日记 2025/9/6 22:57:33

微服务之间调用外键“翻译”的方法概述

写在前面的话：减少strean流操作，减少多层嵌套for循环。使用普通for循环和map的方式进行转换， 第一步查询数据 List<Student> findList studentDao.findList(findMap); 第二步准备遍历和赋值 if(CollectionUtil.isNotEmpty(findLis…...

编程日记 2025/9/8 10:59:41

Java学习——day25（多线程基础与线程创建方式）

文章目录 1. 多线程基础1.1 线程的概念1.2 线程的生命周期 2. 创建线程的方式2.1 继承 Thread 类2.2 实现 Runnable 接口 3. 实践：编写简单多线程程序4. 总结与思考 1. 多线程基础 1.1 线程的概念线程 (Thread)： 程序执行的最小单元，一个进…...

编程日记 2025/9/16 14:12:16

2025前端面试题

Vue 3 比 Vue 2 更快的原因 Vue 3 使用 JavaScript 的 Proxy 替代了 Vue 2 中的 Object.defineProperty 来实现响应式系统。Proxy 可以拦截对象的所有操作，无需像 Object.defineProperty 那样单独定义每个属性的 getter 和 setterVue 3 还引入了静态树提升&#xf…...

编程日记 2025/9/17 20:20:38

2025-04-09 吴恩达机器学习6——神经网络(1)：介绍

文章目录 1 神经网络介绍1.1 起源与发展1.2 生物神经元 vs. 人工神经元1.3 学习建议 2 案例：T 恤预测2.1 基础概念2.2 需求预测示例2.3 多隐藏层神经网络2.4 神经网络的优势 3 案例：图像感知3.1 计算机视觉任务3.2 神经网络架构 1 神经网络介绍 1.1 起源…...

编程日记 2025/9/14 10:03:17

Win11新功能更新：中文语音控制、游戏体验提升、锁屏更多广告

近日，微软在Windows 11发布预览版（Insider Release Preview Channel）中公布了即将正式推送的一系列新功能。这些更新体现了微软“持续创新”策略——不再依赖传统大型版本更新，而是以更高频率为用户带来功能改进。这一波新功能覆盖…...

编程日记 2025/9/11 9:26:42

Cursor编程-从入门到精通__0409

早期的Github Copilot 最近更新了，支持Agent编程，字节跳动Trae使用（免费），但成熟程度不如Cursor，Cursor前50次免费 Copilot VS Cursor*** 1，Cursor VSCode 二次开发，IDE级别 2&…...

编程日记 2025/9/15 20:14:12

【Leetcode-Hot100】移动零

题目解答首先，使用的解题思路是：使用两个指针，分别指向数组的第一个0元素位置，以该元素位置1为起始点寻找接下来第一个非0元素位置。二者确定后，对其进行交换。随后继续寻找下一个0元素位置。重复上述操作。但第一…...

编程日记 2025/9/16 22:54:07

【力扣hot100题】（079）划分字母区间

感觉智商又回来了（松气）。方法大概是先建立哈希表遍历数组记录每一个字母位置的跨度，然后再遍历数组，每次遇到跨度大于目前长度的字母，就将目前长度延申跨度的长度，然后继续遍历，知道位置已经…...

编程日记 2025/9/15 20:25:16

更改CMD背景图片

1.下载microsoft powershell 总之,电脑里面要有microsoft powershell这个应用如下所示进入界面后, 依次点击命令提示符和外观。进入后,修改背景图片 2. 查看最终效果最终我们打开CMD界面, 然后查看。最终结果大功告成...

编程日记 2025/8/21 17:06:46

如何利用AI工具进行抠图

软件介绍 AIArty Image Matting是一款AI抠图软件，为了方便大家使用，我已经将软件所需的模型下载好。首先要进行软件安装并运行，之后将“model”压缩包解压，把解压后的文件复制粘贴到“C:\ProgramData\Aiarty\ImageMatting”文件…...

编程日记 2025/9/10 8:48:42

一个很好用的vue2在线签名组件

在前端开发的日常工作中，我们常常会遇到需要用户进行在线签名的需求，比如电子合同签署、表单确认等场景。最近，我在项目里使用了一款极为好用的 Vue2 在线签名组件，今天就来和大家分享一下使用心得。效果图上代码在 views 下…...

编程日记 2025/9/15 16:45:59

软考高级-系统架构设计师案例题-软件架构设计

文章目录软件架构设计质量属性效用树，质量属性判断必背概念架构风格对比MVC架构J2EE四层结构面向服务架构SOA企业服务总线ESB历年真题【问题1】 （12分)【问题2】（13分） 参考答案历年真题【问题1】（12分）【…...

编程日记 2025/9/10 4:36:06

计算机网络笔记-分组交换网中的时延

一、分组交换网络中的四种时延类型 1. 排队时延在队列中，当分组在链路上等着被传输时的时延为排队时延，一个分组的排队时延长度取决于该分组前方等待传输的分组数量，如果排队队列为空，且没有正在传输的分组那么该分组的排队时延…...

编程日记 2025/9/9 6:59:53

数据结构与算法-图论-复习2（差分约束，强连通分量，二分图，LCA，拓扑排序，欧拉路径和欧拉回路）

7. 差分约束原理差分约束系统是一种特殊的不等式组，形如 xi−xj≤c。可以将其转化为图论中的最短路或最长路问题。最短路求最大值：当我们要找出满足所有不等式的最大解时，使用最短路算法。对于不等式 xi−xj≤c，可以…...

编程日记 2025/9/12 16:21:01

git强制更新本地分支

你的需求是希望自动拉取所有远程分支，并且在分支间存在冲突时自动覆盖本地内容（不保留差异）。以下是优化后的解决方案： 最终解决方案（全自动强制覆盖） git fetch --all && for branch in $(git …...

编程日记 2025/9/11 13:42:30

PH热榜 | 2025-04-09

1. EZsite AI 标语：构建能够秒级产生收入的人工智能应用。介绍：EZsite AI 让任何人都能轻松创建专业的网站和应用，不需要编写代码。它自动保存您的数据库信息，内置的 AI 聊天机器人能帮助您捕获潜在客户，并且通过 A…...

编程日记 2025/8/26 1:29:57

进度管理__制订进度计划_资源平衡和资源平滑

本文讲解的资源平衡与资源平滑，是制订进度计划的工具与技术的第3项： 资源优化。 1. 资源平衡资源平衡是为了在资源需求与资源供给之间取得平等， 根据资源制约因素对开始日期和完成日期进行调整的一种技术。如果共享资源或关键资源只在特定…...

编程日记 2025/9/9 1:33:17

【力扣hot100题】（080）爬楼梯

让我们掌声恭迎动态规划的始祖—— 最基础的动态规划，原始方法是维护一个数组，每次记录到该阶梯的方案数量，每次的数量是到上一个阶梯的方案数量加上到上上一阶梯的方案数量，因为只有两种走法。进阶可以优化空间复杂度&#xf…...

编程日记 2025/8/30 9:02:43

redis_exporter服务安装并启动

redis_exporter服务安装并启动 1、介绍2、下载redis_exporter3、解压缩文件4、启动redis_exporter服务 1、介绍 Redis Exporter 是 Prometheus 官方推荐的 Redis 监控数据导出工具，用于将 Redis 实例的性能指标暴露为 Prometheus 可抓取的格式。 2、下载redis_exp…...

编程日记 2025/9/12 16:19:53

Spring Security 的核心配置项详解，涵盖认证、授权、过滤器链、HTTP安全设置等关键配置，结合 Spring Boot 3.x 版本最佳实践

以下是 Spring Security 的核心配置项详解，涵盖认证、授权、过滤器链、HTTP安全设置等关键配置，结合 Spring Boot 3.x 版本最佳实践： 1. 核心注解与配置类 (1) 启动安全配置 // 启动Web安全配置（推荐方式） Configura…...

编程日记 2025/9/9 15:51:46

Spring Boot 3.x 下 Spring Security 的执行流程、核心类和原理详解，结合用户描述的关键点展开说明，并以表格总结

以下是 Spring Boot 3.x 下 Spring Security 的执行流程、核心类和原理详解，结合用户描述的关键点展开说明，并以表格总结： 1. Spring Security 核心原理 Spring Security 通过 Filter 链实现安全控制，其核心流程如下&#xff1a…...

编程日记 2025/9/15 14:07:38

[leetcode]判断质数

一.判断质数 1.1 什么是质数质数（素数）就是只可以被自己和1整除的数叫做素数/质数 1.2判断方法 #include<bits/stdc.h> using namespace std; bool isPrime(int num) { if(num < 1) { return false;//a number less of …...

编程日记 2025/9/9 6:01:12

【结肠息肉AI论文集】Cross-level Feature Aggregation Network for Polyp Segmentation

标注：同样是一期结肠息肉论文写作评鉴摘要从结肠镜图像中准确分割息肉在结直肠癌的诊断和治疗中起着关键作用。尽管在息肉分割领域已经取得了一定的成效，但仍存在诸多挑战。息肉通常具有多种大小和形状，并且息肉与其周围区域之间没有明显…...

编程日记 2025/9/10 1:28:12

Redis缓存之预热、击穿、穿透、雪崩

面试切入点缓存预热什么是预热？ mysql假如新增100条记录，一般默认以mysql为准作为底单数据，如何同步到redis(布隆过滤器)，这100条合法数据？？ 为什么需要预热？ mysql有100条新记录&#xff0…...

编程日记 2025/9/6 10:42:39

C++字符串复习

C字符串复习前言为了保证复习高效，以下不包括很简单的内容，例如cin。 C类型字符、字符串输入方法 **char c getchar()**输入单个字符 string类型字符串输入方法 getline(cin, str) 整行输入常用方法 s.substr(pos, len)：截取字…...

编程日记 2025/9/10 8:43:55

一、下载下载地址：https://downloads.mysql.com/archives/community/ 二、安装 1、解压 tar -zxvf mysql-5.7.44-linux-glibc2.12-x86_64.tar.gz 2、创建mysql用户组和用户 # 创建mysql用户组 groupadd mysql# 创建用户并添加到mysql用户组中 useradd -r -g m…...

编程日记 2025/9/15 19:22:59

内存分配中的堆（Memory Heap）详解

在计算机科学中，"堆"这个术语确实容易让人混淆，因为它同时用于描述两种完全不同的概念：数据结构中的堆和内存管理中的堆。上次我们讨论了数据结构中的堆，今天我将详细解释内存分配中的堆（Memory Heap&#x…...

编程日记 2025/9/15 1:38:45

第一版代码

第二版代码

第三版代码

第四版代码

第五版代码

相关文章：