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

《程序员面试金典(第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++)

题目描述 硬币。给定数量不限的硬币&#xff0c;币值为25分、10分、5分和1分&#xff0c;编写代码计算n分有几种表示法。(结果可能会很大&#xff0c;你需要将结果模上1000000007) 示例1: 输入: n 5 输出&#xff1a;2 解释: 有两种方式可以凑成总金额: 55 511111 示例2: 输…...

实体商家做抖音运营如何做矩阵?

商家实体门店如何做好短视频矩阵&#xff1f;这是一个值得深入探讨的问题。在当今的数字化时代&#xff0c;短视频成为越来越多企业吸引用户、提高曝光度的一种重要方式&#xff0c;实体店也不例外。在本文中&#xff0c;我们将提供一些实用的建议&#xff0c;帮助实体店如何做…...

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判断是否是完全二叉树<二叉树的遍历> 在学习二叉树遍历之前我们先了解下二叉树的概念。 二叉树是&#xff1a; 1.空树 2.非空…...

linux查看硬件信息

dmidecode用于在linux下获取硬件信息&#xff0c;遵循SMBIOS/DMI标准&#xff0c;可获取包括BIOS、系统、主板、处理器、内存、缓存等等硬件信息 1、查看CPU信息cat /proc/cpuinfo、lscpu 型号&#xff1a;cat /proc/cpuinfo|grep name|cut -f2 -d:|uniq -c 物理核&#xff1a…...

吐血整理,互联网大厂最常见的 1120 道 Java 面试题(带答案)整理

前言 作为一个 Java 程序员&#xff0c;你平时总是陷在业务开发里&#xff0c;每天噼里啪啦忙敲着代码&#xff0c;上到系统开发&#xff0c;下到 Bug 修改&#xff0c;你感觉自己无所不能。然而偶尔的一次聚会&#xff0c;你听说和自己一起出道的同学早已经年薪 50 万&#x…...

RabbitMQ如何避免消息丢失

目录1.生产者没有成功把消息发送到MQ2.RabbitMQ接收到消息之后丢失了消息3.消费者弄丢了消息前言 首先明确一点一条消息的传送流程&#xff1a;生产者->MQ->消费者 我们根据这三个依次讨论 1.生产者没有成功把消息发送到MQ 丢失的原因&#xff1a;因为网络传输的不稳定…...

做算法题的正确姿势(不断更新)

不停的反思自己&#xff0c;总结建议 做一道算法题&#xff0c;不能去死磕。 如果看一道题&#xff0c;半小时内&#xff0c;没有清晰的思路&#xff0c;就看题解&#xff01;&#xff01;&#xff01;你可能觉得你有点思路&#xff0c;就往里死钻&#xff0c;结果可能就像进…...

p85 CTF夺旗-JAVA考点反编译XXE反序列化

数据来源 图片来源 Java 常考点及出题思路 考点技术&#xff1a;xxe&#xff0c;spel 表达式&#xff0c;反序列化&#xff0c;文件安全&#xff0c;最新框架插件漏洞等 设法间接给出源码或相关配置提示文件&#xff0c;间接性源码或直接源码体现等形式 https://www.cnblog…...

FastJson——JSO字符串与对象的相互转化

一、FastJson介绍 ​ Fastjson是阿里巴巴的开源SON解析库它可以解析JSON格式的字符串&#xff0c;支持将java Bean序列化为ISON字符串&#xff0c;也可以从JSON字符串反序列化到JavaBean。 Fastjson的优点 速度快 fastjson相对其他JSON库的特点是快&#xff0c;从2011年fastj…...

《程序员面试金典(第6版)》面试题 08.08. 有重复字符串的排列组合(回溯算法,全排列问题)C++

题目描述 有重复字符串的排列组合。编写一种方法&#xff0c;计算某字符串的所有排列组合。 示例1: 输入&#xff1a;S “qqe” 输出&#xff1a;[“eqq”,“qeq”,“qqe”] 示例2: 输入&#xff1a;S “ab” 输出&#xff1a;[“ab”, “ba”] 提示: 字符都是英文字母。…...

k8s API限流——server级别整体限流和客户端限流

1. 背景 为了防止突发流量影响apiserver可用性&#xff0c;k8s支持多种限流配置&#xff0c;包括&#xff1a; MaxInFlightLimit&#xff0c;server级别整体限流Client限流EventRateLimit, 限制eventAPF&#xff0c;更细力度的限制配置 1.1 MaxInFlightLimit限流 apiserver…...

在华为做了三年软件测试被裁了,我该怎么办

近年来&#xff0c;随着经济环境的变化和企业战略的调整&#xff0c;员工被裁员的情况变得越来越普遍。无论是因为企业经营困难还是因为业务调整&#xff0c;员工们都可能面临被裁员的风险。如果你也遇到了这样的情况&#xff0c;那么你应该怎么办呢&#xff1f; 首先&#xf…...

Spring cloud 限流的多种方式

在频繁的网络请求时&#xff0c;服务有时候也会受到很大的压力&#xff0c;尤其是那种网络攻击&#xff0c;非法的。这样的情形有时候需要作一些限制。本文主要介绍了两种限流方法&#xff0c;感兴趣的可以了解一下 目录 一、实战基于 Spring cloud Gateway 的限流 二、基于阿…...

Linux命令·top

top命令是Linux下常用的性能分析工具&#xff0c;能够实时显示系统中各个进程的资源占用状况&#xff0c;类似于Windows的任务管理器。下面详细介绍它的使用方法。top是一个动态显示过程,即可以通过用户按键来不断刷新当前状态.如果在前台执行该命令,它将独占前台,直到用户终止…...

springmvc之系列文章

springmvc之编程步骤 springmvc初始化过程 用WebServlet和WebFilter干掉web.xml 没有web.xml怎么写web程序 一次GET请求在springmvc中是的处理流程 springMVC的handler都有哪些类型 springmvc主要组件简单介绍 springmvc 的Servlet WebApplicationContext springmvc 的…...

Matlab实现深度学习(附上完整仿真源码)

文章目录简单案例完整仿真代码下载简单案例 深度学习是一种能够自动学习和提取数据特征的机器学习方法&#xff0c;它已经在图像识别、语音识别、自然语言处理等领域取得了显著的成果。而Matlab作为一个强大的数学计算工具&#xff0c;也提供了丰富的深度学习工具箱&#xff0…...

我的谷歌书签

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 数据库技术考点汇总

一、重点知识点 基本概念&#xff1a;三级模式-两级映像、数据库设计数据库模型&#xff1a;E-R模型、关系模型、关系代数&#xff08;结合SQL语言&#xff09;规范化&#xff1a;函数依赖、健与约束、范式、模式分解事务并发&#xff1a;并发三种问题、三级封锁协议数据库新技…...

学剪辑难吗 如何使用会声会影2023做剪辑视频

很多剪辑初学者都问过一个问题&#xff0c;学剪辑难吗&#xff1f;其实不论学什么&#xff0c;只要用心学都不难&#xff0c;今天我们就来讲讲如何学做剪辑视频&#xff0c;感兴趣的小伙伴们不要走开&#xff01;一、学剪辑难吗 其实学剪辑并不是件难事&#xff0c;但是需要掌握…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...