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

518. 零钱兑换 II(力扣LeetCode)

文章目录

  • 518. 零钱兑换 II
    • 题目描述
    • 动态规划
      • 一维数组
        • 为什么不能交换两个for循环的顺序?
      • 二维数组

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

提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

动态规划

一维数组

这段代码是在解决一个称为"零钱兑换 II"的动态规划问题。具体来说,它计算了使用一个无限数量的不同面额硬币凑成某个总金额的所有可能组合的数目。代码使用了C++语言。下面是对这段代码的逐行解释:

// 定义一个Solution类
class Solution {
public:// 定义并实现一个名为change的公共成员函数int change(int amount, vector<int>& coins) {// dp定义了一个整型向量(dp数组),大小为amount + 1,所有值初始化为0vector<int>dp(amount+1, 0);// 将dp数组的第一项设置为1,这表示金额为0的话有1种方式(就是不用任何硬币)dp[0] = 1;// 遍历coins数组,i为索引,从0开始到coins.size() - 1for(int i = 0; i < coins.size(); i++)// 从当前硬币面额coins[i]开始,直到总金额for(int j = coins[i]; j <= amount; j++)// 更新dp[j]的值:dp[j] = dp[j] + dp[j - coins[i]]// 这表示加上用当前的硬币面额coins[i]凑出金额j的新组合数dp[j] += dp[j - coins[i]];// 最后返回dp数组的最后一项,即凑成总金额amount的组合数return dp[amount];}
};

解释一下这个动态规划的核心思想:

  • dp数组的定义:dp[i]表示凑成总金额为i的硬币组合数。
  • 初始化:由于凑成总金额为0的方式只有一种,就是不使用任何硬币,所以初始化dp[0] = 1。
  • 外层循环:遍历每一种硬币。
  • 内层循环:对于每一种硬币,更新金额从硬币面额到总金额的所有dp值。
  • 状态转移方程:dp[j] += dp[j - coins[i]]的含义是,对于每个金额j,考虑当前的硬币面额coins[i],如果我们知道了组成金额j - coins[i]的组合数(即dp[j - coins[i]]),那么就可以通过添加一个coins[i]硬币来得到金额j的一个新的组合。所以,我们要将组成金额j - coins[i]的所有组合数加到dp[j]上。

这个算法的时间复杂度是O(n*m),n是金额amount,m是硬币种类数。空间复杂度是O(n),因为我们使用了一个n + 1大小的dp数组。

为什么不能交换两个for循环的顺序?

在这个特定的动态规划问题中,两个for循环的顺序决定了硬币组合数是如何被计算的,特别是它们影响了状态转移方程的更新方式。如果交换了循环的顺序,将会改变动态规划算法的整个逻辑。

原始顺序(先遍历硬币,然后遍历金额)的循环确保了以下几点:

  1. 组合性:当计算dp[j]时(即凑成金额j的方法数),算法仅考虑使用当前硬币和之前考虑过的硬币的组合。这意味着,对于每个硬币,你都是在累积之前的结果上增加新的可能性。

  2. 无重复:这个顺序确保了在计算组合数时,相同面额的硬币不会被重复计算。即我们不会得到多个考虑顺序不同但实际上相同的硬币组合。

  3. 有序:由于每次循环都是在之前硬币的基础上加上新硬币,因此所有的组合都是以一种有序的方式生成的。

如果交换了for循环的顺序,算法将会改变上述逻辑,导致以下问题:

  • 每次计算dp[j]时,都会考虑所有硬币,这意味着同一金额会被重复计算多次,从而破坏了动态规划的基本原则。
  • 容易出现重复组合,因为对于每个金额,你都在尝试所有的硬币,无法保证硬币使用的唯一顺序,从而可能导致重复的组合方式被计数。
  • 缺乏顺序性,因为你在每个金额的计算中都包含了所有的硬币,这样就会有多种硬币组合顺序产生相同的金额,这些都被错误地算作不同的组合。

因此,保持原始的循环顺序对于解决这个动态规划问题是很重要的,它确保了算法的正确性和效率。

二维数组

这段代码是解决"零钱兑换 II"问题的动态规划解法。下面是对代码的详细注释:

class Solution {
public:int change(int amount, vector<int>& coins) {// 初始化动态规划表格。行数为coins.size()+1,代表0到coins.size个硬币,列数为amount+1,代表0到amount的金额。// dp[i][j]表示使用前i种硬币凑成金额j的方法数。vector<vector<int>> dp(coins.size()+1,vector<int>(amount+1,0));// base case:当金额为0时,即j=0,不使用任何硬币就能凑齐,因此方法数为1。dp[0][0]=1;// 遍历所有的硬币种类for(int i=1;i<=coins.size();i++){// 对于每一种硬币,遍历所有可能的金额for(int j=0;j<=amount;j++){// dp[i][j]首先继承dp[i-1][j]的值,即不使用第i种硬币时凑成金额j的方法数。dp[i][j]=dp[i-1][j];// 如果当前金额j大于等于当前考虑的硬币面额coins[i-1],// 则可以考虑使用这种硬币。此时的方法数为dp[i][j-coins[i-1]],// 加上这种硬币之前的方法数,因为dp[i][j-coins[i-1]]已经计算了使用前i种硬币凑成金额j-coins[i-1]的方法数。if(j>=coins[i-1])dp[i][j]+=dp[i][j-coins[i-1]];}}// 返回使用所有硬币凑成总金额amount的方法数。return dp[coins.size()][amount];}
};

核心思想:

  • 动态规划表dp的大小为(coins.size()+1) * (amount+1)dp[i][j]表示使用前i种硬币(其中硬币种类从0开始编号)凑成金额j的方法数。
  • 初始化dp[0][0]=1表示不使用任何硬币凑成金额0的方法有1种。
  • 外层循环遍历硬币种类,内层循环遍历可能的金额。
  • 对于每一种硬币coins[i-1]和每一个金额j,如果j大于等于当前硬币的面额,我们有两个选择:不使用当前的硬币(继承dp[i-1][j]的值),或者使用当前的硬币(dp[i][j-coins[i-1]]加上当前硬币的数量)。
  • 最终,dp[coins.size()][amount]是使用所有硬币凑成金额amount的方法数。

相关文章:

518. 零钱兑换 II(力扣LeetCode)

文章目录 518. 零钱兑换 II题目描述动态规划一维数组为什么不能交换两个for循环的顺序&#xff1f; 二维数组 518. 零钱兑换 II 题目描述 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数…...

01串的熵(蓝桥杯)

文章目录 01串的熵问题描述答案&#xff1a;11027421题意解释暴力枚举 01串的熵 问题描述 对于一个长度为n的01串 S x 1 x 2 x 3 x_{1}x_{2}x_{3} x1​x2​x3​… x n x_{n} xn​&#xff0c;香农信息熵的定义为 H(S) − ∑ 1 n p ( x i ) l o g 2 ( p ( x i ) ) -\sum _{1…...

Rust 基础语法和数据类型

数据类型 Rust提供了一系列的基本数据类型&#xff0c;包括整型&#xff08;如i32、u32&#xff09;、浮点型&#xff08;如f32、f64&#xff09;、布尔类型&#xff08;bool&#xff09;和字符类型&#xff08;char&#xff09;。此外&#xff0c;Rust还提供了原生数组、元组…...

【Java SE】10 String类

目录 1. String类的重要性 2.常用方法 2.1字符串构造 2.2 String对象的比较 2.3字符串查找 2.4转化 2.5字符串替换 2.6字符串拆分 2.7字符串截取 2.8其他操作方法 2.9字符串的不可变性 2.10字符串修改 3. StringBuffer和StringBuilder 3.1StringBuilder的介绍 4.…...

web蓝桥杯真题:新鲜的蔬菜

代码&#xff1a; .box {display: flex; } #box1 {align-items: center;justify-content: center; }#box2 {justify-content: space-between; } #box2 .item:nth-child(2) {align-self: end; }#box3 {justify-content: space-between; } #box3 .item:nth-child(2) {align-self…...

超声波清洗机能洗哪些东西?洗眼镜超声波清洗机推荐

在现代生活中&#xff0c;人们对清洁卫生的要求越来越高&#xff0c;尤其是对一些细小物件的清洁。眼镜作为我们日常生活中不可或缺的物品&#xff0c;清洁保养更是至关重要。传统的清洗方式可能无法完全清洁眼镜表面的细菌和污垢&#xff0c;于是超声波清洗机成为了很多人的选…...

[C++][算法基础]走迷宫(BFS)

给定一个 nm 的二维整数数组&#xff0c;用来表示一个迷宫&#xff0c;数组中只包含 0 或 1&#xff0c;其中 0 表示可以走的路&#xff0c;1 表示不可通过的墙壁。 最初&#xff0c;有一个人位于左上角 (1,1)(1,1) 处&#xff0c;已知该人每次可以向上、下、左、右任意一个方…...

C语言字符串左旋

一、前言 这个题目的完整题目是这样子的。 二、我们实现这个编程的思路 2.1暴力破解思想 假如有一个数组里面的字符串为”abcdef“&#xff0c;我们这时候就这样先将字符”a“移到最后再将其余的字符前移。 2.2三步移动法 同样我们还是假设一个数组里面存的是字符串”abcd…...

Linux 中断会产生嵌套吗?

文章目录 1. 前言2. Linux 中断是否会嵌套&#xff1f;2.1 分析背景2.2 中断处理抢占、嵌套可能性分析2.3 中断处理抢占、嵌套小结 3. 参考资料 1. 前言 限于作者能力水平&#xff0c;本文可能存在谬误&#xff0c;因此而给读者带来的损失&#xff0c;作者不做任何承诺。 2. …...

嵌入式ARM版本银河麒麟操作系统V10SP1安装OPenGauss数据库

前言&#xff1a; 官网提供了非常完整的openGauss安装步骤。 https://opengauss.org/zh/download/archive/列举一下个人的使用环境&#xff1a; 麒麟V10 rk3588工控板&#xff08;ARM&#xff09; openGauss-3.0.5&#xff08;极简版&#xff09;浏览一下官网&#xff0c;可以…...

深度学习八股文

Bert旨在通过联合左侧和右侧的上下文&#xff0c;从未标记文本中预训练出一个深度双向表示模型。因此&#xff0c;BERT可以通过增加一个额外的输出层来进行微调&#xff0c;就可以达到为广泛的任务创建State-of-the-arts 模型的效果&#xff0c;比如QA、语言推理任务。Bert的构…...

jquery 自整理

echarts官方&#xff1a;Documentation - Apache ECharts 1、CheckBox复选框 //选中事件&#xff08;页面点击&#xff09; $(#operateExit).on(ifChecked, function(){ $(input[name"operateExit"]).val(1); }); //非选中事件&#xff…...

MySQL | 加索引报错

报错信息 1170 - BLOB/TEXT column user_name used in key specification without a key length解决方案 分析 这个错误通常是因为尝试在一个包含BLOB或TEXT类型列的列上创建索引时没有指定键的长度。MySQL要求在使用BLOB或TEXT类型列作为索引键时&#xff0c;必须指定键的长…...

前端:自制年历

详细思路可以看我的另一篇文章《前端&#xff1a;自制月历》&#xff0c;基本思路一致&#xff0c;只是元素布局略有差异 ①获取起始位startnew Date(moment().format(yyyy-01-01)).getDay() ②获取总的格子数numMath.ceil(365/7)*7,这里用365或者366计算结果都是一样的371 …...

9.手写JavaScript大数相加问题

一、核心思想 找到两个字符串中最长的长度&#xff0c;对两个字符串在头位置补0达到相等的长度&#xff0c;相加时注意进位和类型转换&#xff0c;特别考虑当相加到第一位是如果仍然有进位不要忽略。此外&#xff0c;js中允许使用的最大的数字为 console.log("最大数&qu…...

FPGA开源项目分享——基于 DE1-SOC 的 String Art 实现

导语 今天继续康奈尔大学FPGA课程ECE 5760的典型案例分享——基于DE1-SOC的String Art实现。 &#xff08;更多其他案例请参考网站&#xff1a; Final Projects ECE 5760&#xff09; 1. 项目概述 项目网址 ECE 5760 Final Project 项目说明 String Art起源于19世纪的数学…...

通过 CLI 和引入的方式使用 React:基础入门

使用React 有两种使用方式&#xff0c;主要有以下几个原因: 灵活性和适应性: 引入的方式可以让开发者在现有的 HTML 页面中快速引入 React,无需设置完整的项目环境。这适合小型或原型项目。 CLI 方式则更适合用于构建大型复杂的 React 应用程序,因为它提供了更完整的项目结构和…...

第三资本:铸就辉煌非凡的资历

第三资本香港有限公司在在金融投资领域一直以专业精神和不懈追求获得良好名声,近几年在国际资本市场上更是写下了辉煌的章节。针对第三资本而言,专业是基本,也是成功的唯一途径。投资总监刘国海解释道:“金融从业者务必深入把握专业能力,对行业现状敏感,重视风险管控,才能在这个…...

基于激光雷达的袋装水泥智能装车系统有哪些优势?

激光雷达技术在水泥机械智能化中发挥着举足轻重的作用&#xff0c;特别在袋装水泥智能装车系统的应用中表现得尤为突出。 由因泰立科技精心打造的基于激光雷达的袋装水泥智能装车系统&#xff0c;不仅大幅缩短了装车码垛的时间&#xff0c;降低了工人的劳动强度&#xff0c;还显…...

实战自动化修改主机名

一、主程序 #!/bin/bash# 设置主机名为node01 set_hostname() {local new_hostname$1echo "正在设置主机名为 $new_hostname ..."# 使用hostnamectl设置主机名hostnamectl set-hostname $new_hostname# 检查主机名是否更改成功if [ "$(hostname)" "…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...