力扣 322. 零钱兑换

题目来源:https://leetcode.cn/problems/coin-change/description/

 C++题解(来源代码随想录):题目中说每种硬币的数量是无限的,可以看出是典型的完全背包问题。动规五部曲分析如下:

  1. 确定dp数组以及下标的含义。dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
  2. 确定递推公式。凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]。递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
  3. dp数组如何初始化。首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0; 其他下标对应的数值呢?考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
  4. 确定遍历顺序。本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数
  5. 举例推导dp数组
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过,不跳过+1会超出int范围。dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89905.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Synopsys EDA数字设计与仿真

参考如下文章安装Synopsys EDA开发工具 https://blog.csdn.net/tugouxp/article/details/132255002?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22132255002%22%2C%22source%22%3A%22tugouxp%22%7D Synopsys EDA工具的结构 下…

面试总结-webpack/git

说说你对webpack的理解 webpack 是一个静态模块打包器&#xff0c;整个打包过程就像是一条生产线&#xff0c;把资源从入口放进去&#xff0c;经过一系列的加工&#xff08;loader&#xff09;&#xff0c;最终转换成我们想要的结果&#xff0c;整个加工过程还会有监控&#x…

接口测试和功能测试的区别

接口测试和功能测试的区别&#xff1a; 2023最新Jmeter接口测试从入门到精通&#xff08;全套项目实战教程&#xff09; 本文主要分为两个部分&#xff1a; 第一部分&#xff1a;主要从问题出发&#xff0c;引入接口测试的相关内容并与前端测试进行简单对比&#xff0c;总结两者…

利用SimpleDateFormat或者LocalDateTime生成格式为“yyyy-MM-dd HH:mm:ss“的当前时间

java程序&#xff1a; // 利用LocalDateTime生成格式为"yyyy-MM-dd HH:mm:ss"的当前时间 DateTimeFormatter formatter DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss"); LocalDateTime now LocalDateTime.now(); String time1 now.format(format…

(7)(7.4) 集结航点

文章目录 7.4.1 概述 7.4.2 设置集结航点 7.4.3 飞行示例 7.4.4 附录 7.4.1 概述 通常情况下&#xff0c;当固定翼或旋翼飞机进入"返回发射"(Return to Launch (RTL))模式&#xff08;通常由自动驾驶仪失控保护触发&#xff09;(failsafe)时&#xff0c;默认行为…

Spring Task入门案例

Spring Task 是Spring框架提供的任务调度工具&#xff0c;可以按照约定的时间自动执行某个代码逻辑。 定位&#xff1a;定时任务框架 作用&#xff1a;定时自动执行某段Java代码 强调&#xff1a;只要是需要定时处理的场景都可以使用Spring Task 1. cron表达式 cron表达式…

spring之AOP简单介绍

1.AOP的概念 AOP&#xff0c;Aspect Oriented Programming&#xff0c;面向切面编程&#xff0c;是对面向对象编程OOP的升华。OOP是纵向对一个 事物的抽象&#xff0c;一个对象包括静态的属性信息&#xff0c;包括动态的方法信息等。而AOP是横向的对不同事物的抽象&#xff0c;…

设计模式(5)代理模式

一、介绍&#xff1a; 【Subject/抽象角色】定义了RealSubject和Proxy的共用接口&#xff0c;这样就可以在任何使用RealSubject的地方都可以使用Proxy 【RealSubject/真实角色】定义Proxy所代表的真实实体 【Proxy/代理角色】保存一个引用使得代理可以访问实体&#xff0c;并…

【Linux】多线程——线程引入 | 线程控制

文章目录 一、Linux多线程1. 线程概念2. 线程创建3. 线程和进程4. 线程的优缺点 二、线程控制1. 线程创建2. 线程终止3. 线程等待4. 线程分离5. 线程局部存储 三、线程封装 一、Linux多线程 一级页表和二级页表都是key/val模型&#xff0c;一级页表的key是第一份的10个比特位&a…

css的transform样式计算-第一节

本文作者为 360 奇舞团前端开发工程师 引言 在使用 css 样式进行样式的缩放、旋转等设置时&#xff0c;思考了一下它的较浅层的原理&#xff0c;恩&#xff0c;这个阶段都 是一些初高的数学计算&#xff0c;从新看这里的时候顺便捡了捡初高中的数学&#xff0c;比如三角函数之类…

利用 Splashtop Enterprise 改善公司的网络安全

在我们日益数字化的世界中&#xff0c;对强有力的网络安全措施的需求从未像现在这样迫切。随着组织扩大其数字足迹并采用远程办公解决方案&#xff0c;他们面临着一系列不断变化的挑战。 威胁行为者不断寻找利用漏洞的新方法&#xff0c;这使得企业保持领先地位至关重要。俗话…

htmlCSS-----弹性布局

目录 前言 什么是弹性布局 样式 学习概要 容器和项目 弹性布局的排列方式 1.横向排列&#xff08;默认样式&#xff09; 2.父元素容器的属性&#xff08;*5&#xff09; &#xff08;1&#xff09;主轴 代码示例&#xff1a; &#xff08;2&#xff09;交叉轴 3.子元素…

Stable Diffusion WebUI安装和使用教程(Windows)

目录 下载Stable Diffusion WebUI运行安装程序&#xff0c;双击webui.bat界面启动插件安装&#xff08;github&#xff09;模型下载(有些需要魔法&#xff09;安装过程遇到的大坑总结参考的博客 整个过程坑巨多&#xff0c;我花了一个晚上的时间才全部搞定,本教程针对有编程基础…

分布式系统监控zabbix安装部署及使用

分布式系统监控zabbix安装部署及使用 一.zabbix监控 1.什么是zabbix zabbix&#xff1a;是一款开源免费的&#xff0c;自动化发现服务与网络设备的分布式监控&#xff0c;可以监视应用层服务并以web前端页面集中管理并展示。 2.zabbix功能 监控服务器cpu负载、服务器内存使…

adb 通过wifi连接手机

adb 通过wifi连接手机 1. 电脑通过USB线连接手机2. 手机开启USB调试模式&#xff0c;开启手机开发者模式3.手机开启USB调试模式 更多设置-》开发者选项-》USB调试4.点击Wi-Fi 高级设置&#xff0c;可以查看到手机Wi-Fi的IP地址&#xff0c;此IP地址adb命令后面的ip地址&#xf…

2023年国赛数学建模思路 - 案例:ID3-决策树分类算法

文章目录 0 赛题思路1 算法介绍2 FP树表示法3 构建FP树4 实现代码 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法&#xff0c;就是频繁模…

消息队列(11) - 通信协议的设计

目录 通信协议设计代码实现 通信协议设计 对于我们客户端与服务器之间的通信协议我们约定如下&#xff1a; 具体的协议设计: 之后我们传递的参数也是这些 关于 type其实是在描述当前这个请求 、 响应是在调用那个API 约定如下 对于channel ,是tcp链接中的一个逻辑上的链接,…

液体神经网络:LNN是个啥概念?

一、说明 在在人工智能领域&#xff0c;神经网络已被证明是解决复杂问题的非常强大的工具。多年来&#xff0c;研究人员不断寻求创新方法来提高其性能并扩展其能力。其中一种方法是液体神经网络&#xff08;LNN&#xff09;的概念&#xff0c;这是一个利用动态计算功能的迷人框…

IDEA如何调试Stream API

Stream API现在在实际开发中应用非常广泛&#xff0c;经常会遇到需要调试Stream API的场景&#xff0c;这篇文章主要讲解如何使用IDEA调试Stream Testpublic void test(){Stream.of(10, 20, 30, 40, 50).mapToInt(e->e*10).filter(e->e>200).forEach(System.out::pri…

笔记04:全局内存

一、CUDA内存模型概述 寄存器、共享内存、本地内存、常量内存、纹理内存和全局内存 一个核函数中的线程都有自己私有的本地内存。 一个线程块有自己的共享内存&#xff0c;对同一个线程块中所有的线程都可见&#xff0c;其内容持续线程块的整个生命周期。 所有线程都可以访问…