《程序员面试金典(第6版)》 面试题 08.11. 硬币(动态规划,组合问题,C++)
题目描述
硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007)
示例1:
- 输入: n = 5
输出:2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
- 输入: n = 10
输出:4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明:
- 你可以假设:0 <= n (总金额) <= 1000000
解题思路与代码
这道题我拿到手上,就有了一种拿动态规划去解决它的冲动。所以让我们来看看这道题拿动态规划怎么去解决。
方法一 :动态规划
第一步,拿到这道题,先分析dp数组的下标以及含义是什么?
- 定义一个一维数组dp,其中dp[i]表示组成金额n的钱的不同表示方法的数量。
第二步,去确定状态转移方程式什么?
- 对于每一个币值(1,5,10,25),
依次从当前硬币的价值处开始遍历直到最大金额n处停止,一共有多少种方法,那么对于当前金额j,可以得出递推公式:dp[j] = (dp[j] + dp[j - 当前币值]) % 1000000007
第三步,去初始化dp数组
- 由于下一步的结果永远都是由上一步所去推出来的,所以我们要直到第一步的数值是多少,才好去做下面的推导
- 我们要将初始化dp[0]为1,因为有一种表示方法是使用0个硬币组成0分。其余元素初始化为0。
第四步,确定如何遍历dp数组。
- 我们要用一个双层的for循环去遍历这个dp数组,这是因为,我们一共有4种硬币的面值。所以我们要一次选择每一种面值的数额去作为其实遍历的点,直到达到题目要求的n时停止。
- 那么代码大概就是这样:
for(int& coin : coins)for(int i = coin; i < n+1; ++i)dp[i] = (dp[i] + dp[i - coin])%MOD;
第五步,举例推导dp数组
- 这一步自己在纸上画一画就好了
具体的解决代码如下:
class Solution {
public:int waysToChange(int n) {int MOD = 1000000007;vector<int> dp(n+1);vector<int> coins{1,5,10,25};dp[0] = 1;for(int& coin : coins)for(int i = coin; i < n+1; ++i)dp[i] = (dp[i] + dp[i - coin])%MOD;return dp[n];}
};

复杂度分析
时间复杂度:O(n),其中n为输入金额。这是因为代码中有两层循环,第一层循环遍历硬币,它是一个常数4(币值:1, 5, 10, 25),第二层循环遍历所有金额,从硬币面值到n。因此,总时间复杂度是O(4n),可以简化为O(n)。
空间复杂度:O(n),其中n为输入金额。代码中主要的空间消耗来自dp数组,它的大小为n + 1。因此,空间复杂度为O(n)。
总结
这道题是动态规划里的一道组合类问题。我尝试着把这道题往0-1背包去靠,结果有点费劲。不如就像我这么去解释。
不要硬生生的划分给0-1背包,这就是一道动态规划的组合问题而已。
难度确实始终,也很好理解。但你要往0-1背包去靠,那就很难理解了。我个人感觉。
相关文章:
《程序员面试金典(第6版)》 面试题 08.11. 硬币(动态规划,组合问题,C++)
题目描述 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示例1: 输入: n 5 输出:2 解释: 有两种方式可以凑成总金额: 55 511111 示例2: 输…...
实体商家做抖音运营如何做矩阵?
商家实体门店如何做好短视频矩阵?这是一个值得深入探讨的问题。在当今的数字化时代,短视频成为越来越多企业吸引用户、提高曝光度的一种重要方式,实体店也不例外。在本文中,我们将提供一些实用的建议,帮助实体店如何做…...
java 双列集合Map 万字详解
目录 一、前言 二、概述 三、特点 四、常用方法 1. V put(K key, V value) : Δ代码演示 : 2. V get(Object key) : Δ代码演示 : 3. V remove(Object key) : Δ代码演示 : 4. int size() : Δ代码演示 : 5. default V replace(K key, V value) : Δ代码演示 : 6. bo…...
【数据结构】二叉树<遍历>
【二叉树遍历】|-前序-中序-后序-层序-|<二叉树的遍历>1.前序遍历【递归】2.中序遍历【递归】3.后序遍历【递归】4.层序遍历【非递归】4.1判断是否是完全二叉树<二叉树的遍历> 在学习二叉树遍历之前我们先了解下二叉树的概念。 二叉树是: 1.空树 2.非空…...
linux查看硬件信息
dmidecode用于在linux下获取硬件信息,遵循SMBIOS/DMI标准,可获取包括BIOS、系统、主板、处理器、内存、缓存等等硬件信息 1、查看CPU信息cat /proc/cpuinfo、lscpu 型号:cat /proc/cpuinfo|grep name|cut -f2 -d:|uniq -c 物理核:…...
吐血整理,互联网大厂最常见的 1120 道 Java 面试题(带答案)整理
前言 作为一个 Java 程序员,你平时总是陷在业务开发里,每天噼里啪啦忙敲着代码,上到系统开发,下到 Bug 修改,你感觉自己无所不能。然而偶尔的一次聚会,你听说和自己一起出道的同学早已经年薪 50 万&#x…...
RabbitMQ如何避免消息丢失
目录1.生产者没有成功把消息发送到MQ2.RabbitMQ接收到消息之后丢失了消息3.消费者弄丢了消息前言 首先明确一点一条消息的传送流程:生产者->MQ->消费者 我们根据这三个依次讨论 1.生产者没有成功把消息发送到MQ 丢失的原因:因为网络传输的不稳定…...
做算法题的正确姿势(不断更新)
不停的反思自己,总结建议 做一道算法题,不能去死磕。 如果看一道题,半小时内,没有清晰的思路,就看题解!!!你可能觉得你有点思路,就往里死钻,结果可能就像进…...
p85 CTF夺旗-JAVA考点反编译XXE反序列化
数据来源 图片来源 Java 常考点及出题思路 考点技术:xxe,spel 表达式,反序列化,文件安全,最新框架插件漏洞等 设法间接给出源码或相关配置提示文件,间接性源码或直接源码体现等形式 https://www.cnblog…...
FastJson——JSO字符串与对象的相互转化
一、FastJson介绍 Fastjson是阿里巴巴的开源SON解析库它可以解析JSON格式的字符串,支持将java Bean序列化为ISON字符串,也可以从JSON字符串反序列化到JavaBean。 Fastjson的优点 速度快 fastjson相对其他JSON库的特点是快,从2011年fastj…...
《程序员面试金典(第6版)》面试题 08.08. 有重复字符串的排列组合(回溯算法,全排列问题)C++
题目描述 有重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合。 示例1: 输入:S “qqe” 输出:[“eqq”,“qeq”,“qqe”] 示例2: 输入:S “ab” 输出:[“ab”, “ba”] 提示: 字符都是英文字母。…...
k8s API限流——server级别整体限流和客户端限流
1. 背景 为了防止突发流量影响apiserver可用性,k8s支持多种限流配置,包括: MaxInFlightLimit,server级别整体限流Client限流EventRateLimit, 限制eventAPF,更细力度的限制配置 1.1 MaxInFlightLimit限流 apiserver…...
在华为做了三年软件测试被裁了,我该怎么办
近年来,随着经济环境的变化和企业战略的调整,员工被裁员的情况变得越来越普遍。无论是因为企业经营困难还是因为业务调整,员工们都可能面临被裁员的风险。如果你也遇到了这样的情况,那么你应该怎么办呢? 首先…...
Spring cloud 限流的多种方式
在频繁的网络请求时,服务有时候也会受到很大的压力,尤其是那种网络攻击,非法的。这样的情形有时候需要作一些限制。本文主要介绍了两种限流方法,感兴趣的可以了解一下 目录 一、实战基于 Spring cloud Gateway 的限流 二、基于阿…...
Linux命令·top
top命令是Linux下常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。下面详细介绍它的使用方法。top是一个动态显示过程,即可以通过用户按键来不断刷新当前状态.如果在前台执行该命令,它将独占前台,直到用户终止…...
springmvc之系列文章
springmvc之编程步骤 springmvc初始化过程 用WebServlet和WebFilter干掉web.xml 没有web.xml怎么写web程序 一次GET请求在springmvc中是的处理流程 springMVC的handler都有哪些类型 springmvc主要组件简单介绍 springmvc 的Servlet WebApplicationContext springmvc 的…...
Matlab实现深度学习(附上完整仿真源码)
文章目录简单案例完整仿真代码下载简单案例 深度学习是一种能够自动学习和提取数据特征的机器学习方法,它已经在图像识别、语音识别、自然语言处理等领域取得了显著的成果。而Matlab作为一个强大的数学计算工具,也提供了丰富的深度学习工具箱࿰…...
我的谷歌书签
Form 表单 | Element Plusa Vue 3 based component library for designers and developershttps://element-plus.gitee.io/zh-CN/component/form.html#%E5%AF%B9%E9%BD%90%E6%96%B9%E5%BC%8F three.js exampleshttp://www.yanhuangxueyuan.com/threejs/examples/#software_geo…...
day3 数据库技术考点汇总
一、重点知识点 基本概念:三级模式-两级映像、数据库设计数据库模型:E-R模型、关系模型、关系代数(结合SQL语言)规范化:函数依赖、健与约束、范式、模式分解事务并发:并发三种问题、三级封锁协议数据库新技…...
学剪辑难吗 如何使用会声会影2023做剪辑视频
很多剪辑初学者都问过一个问题,学剪辑难吗?其实不论学什么,只要用心学都不难,今天我们就来讲讲如何学做剪辑视频,感兴趣的小伙伴们不要走开!一、学剪辑难吗 其实学剪辑并不是件难事,但是需要掌握…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
