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

第四十五天 | 322.零钱兑换

题目:322.零钱兑换

尝试解答:

1.确定dp[j]含义:装满容量为j的背包所需要放的硬币个数为dp[j];

2.动态转移方程:dp[j] = dp[j - coins[i]] + 1;

3.遍历顺序:本题应该为组合类题目,不考虑装入的顺序,只在乎硬币个数

        所以先物品后背包,背包容量从小到大。(错)

4.初始化:dp[0] = 1,其余均初始换为0

5.打印dp

代码实现如下,有漏洞,执行不对:

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, 0);dp[0] = 1;int result = INT_MAX;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){// dp[j] = dp[j - coins[i]] + 1;// result = min(dp[j], result);if(j == amount){result = min(dp[j], result);}}}return result;}
};

正确思路:

1.确定dp[j]含义:装满容量为j的背包所需要最少放的硬币个数为dp[j];

2.动态转移方程:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

        本轮要放的物品重量为coins[i],所以背包必须腾出coins[i]这么大的容量留给coins[i],所以之前背包装的重量必须是dp[j - coins[i]]。装了coins[i]后,一共装了dp[j - coins[i]] + 1块硬币,与不装coins[i] 的情况比大小,取其小,得到本轮循环的最优解,就是本次的最少个数。

3.初始化:

        本题初始化比较取巧,之前不管是排列还是组合,dp[0]都初始化为了1,但这到题从测试样例中可以看出,dp[0] = 0。

        其他位置的值如何进行初始化?从本质入手,因为是取其小,必须将他们初始化为INT_MAX,才可以保证在二维数组的第一行可以成功更改值,不会被原来初始化的值覆盖(解释这一点时我习惯从二维数组的角度出发)。

        其实道理和其他题目中,初始化为0的道理是一样的,其他题目如果是取其大max,则初始化为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] = min(dp[j - coins[i]] + 1, dp[j]);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

对于返回-1的条件不是很理解。

循环里的判断条件:如果dp[j - coins[i]] != INT_MAX,那么是不可能通过目前遍历到的物品将背包装满的。

返回值时进行的判断:如果dp[amount] == INT_MAX,那么不可能将背包装满。

相关文章:

第四十五天 | 322.零钱兑换

题目&#xff1a;322.零钱兑换 尝试解答&#xff1a; 1.确定dp[j]含义&#xff1a;装满容量为j的背包所需要放的硬币个数为dp[j]; 2.动态转移方程&#xff1a;dp[j] dp[j - coins[i]] 1; 3.遍历顺序&#xff1a;本题应该为组合类题目&#xff0c;不考虑装入的顺序&#x…...

3D 生成重建011-LucidDreamer 优化SDS过平滑结果的一种探索

3D 生成重建011-LucidDreamer 优化SDS过平滑结果的一种探索 文章目录 0论文工作1论文方法2 效果 0论文工作 文本到3D生成的最新进展标志着生成模型的一个重要里程碑&#xff0c;为在各种现实场景中创建富有想象力的3D资产打开了新的可能性。虽然最近在文本到3D生成方面的进展…...

ES6 笔记04

01 异步函数的使用 es6推出了一种按照顺序执行的异步函数的方法 async 异步函数 async异步函数可以解决promise封装异步代码,调用时一直then链式编程时比较麻烦的问题 定义异步函数: async function 函数名(){ await 表达式1或者函数的调用1 await 表达式2或者函数的调用2 ...…...

中间件-------RabbitMQ

同步和异步 异步调用 MQ MQ优势&#xff1a;①服务解耦 ②异步调用 ③流量削峰 结构 消息模型 RabbitMQ入门案例&#xff0c;实现消息发送和消息接收 生产者&#xff1a; public class PublisherTest {Testpublic void testSendMessage() throws IOException, TimeoutExce…...

flink Data Source数据源

flink Data Source数据源 Source 并行度 非并行&#xff1a;并行度只能为1 并行 基于集合的Source fromElements package com.pxj.sx.flink; import org.apache.flink.configuration.Configuration; import org.apache.flink.configuration.RestOptions; import org.ap…...

网络七层模型与云计算中的网络服务

网络七层模型&#xff0c;也称为OSI&#xff08;Open System Interconnection&#xff09;模型&#xff0c;是由国际标准化组织&#xff08;ISO&#xff09;制定的一个概念性框架&#xff0c;用于描述网络通信过程中信息是如何被封装、传输和解封装的。这一模型将复杂的网络通信…...

word一按空格就换行怎么办?word文本之间添加空格就换行怎么办?

如上图&#xff0c;无法在Connection和con之间添加空格&#xff0c;一按空格就会自动换行。 第一步&#xff1a;选中文本&#xff0c;打开段落。 第二步&#xff1a;点击中文版式&#xff0c;勾选允许西文在单词中间换行。 确定之后就解决一按空格就自动换行啦&#xff01;...

Python 遍历字典的方法,你都掌握了吗

Python中的字典是一种非常灵活的数据结构&#xff0c;它允许通过键来存储和访问值。在处理字典时&#xff0c;经常需要遍历字典中的元素&#xff0c;以下是几种常见的遍历字典的方法。 1. 使用 for 循环直接遍历字典的键 字典的键是唯一的&#xff0c;可以直接通过 for 循环来…...

MySQL 8.4.0 LTS 变更解析:I_S 表、权限、关键字和客户端

↑ 关注“少安事务所”公众号&#xff0c;欢迎⭐收藏&#xff0c;不错过精彩内容~ MySQL 8.4.0 LTS 已经发布 &#xff0c;作为发版模型变更后的第一个长期支持版本&#xff0c;注定要承担未来生产环境的重任&#xff0c;那么这个版本都有哪些新特性、变更&#xff0c;接下来少…...

LeetCode 124 —— 二叉树中的最大路径和

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 二叉树的问题首先我们要想想是否能用递归来解决&#xff0c;本题也不例外&#xff0c;而递归的关键是找到子问题。 我们首先来看看一棵最简单的树&#xff0c;也就是示例 1。这样的一棵树总共有六条路径&#xf…...

美甲店会员预约系统管理小程序的作用是什么

女性爱美体现在方方面面&#xff0c;美丽好看的指甲也不能少&#xff0c;市场中美甲店、小摊不少&#xff0c;也跑出了不少连锁品牌&#xff0c;70后到00后&#xff0c;每个层级都有不少潜在客户&#xff0c;商家需要获取和完善转化路径&#xff0c;不断提高品牌影响力与自身内…...

..堆..

堆 堆是完全二叉树&#xff0c;即除了最后一列之外&#xff0c;上面的每一层都是满的&#xff08;左右严格对称且每个节点都满子节点&#xff09; 最后一列从左向右排序。 默认大根堆&#xff1a;每一个节点都大于其左右儿子&#xff0c;根节点就是整个数据结构的最大值 pr…...

【LLM多模态】综述Visual Instruction Tuning towards General-Purpose Multimodal Model

note 文章目录 note论文1. 论文试图解决什么问题2. 这是否是一个新的问题3. 这篇文章要验证一个什么科学假设4. 有哪些相关研究&#xff1f;如何归类&#xff1f;谁是这一课题在领域内值得关注的研究员&#xff1f;5. 论文中提到的解决方案之关键是什么&#xff1f;6. 论文中的…...

探索Linux中的神奇工具:重定向符的妙用

探索Linux中的神奇工具&#xff1a;重定向符的妙用 在Linux系统中&#xff0c;重定向符是一个强大的工具&#xff0c;用于控制命令的输入和输出&#xff0c;实现数据流的定向。本文将详细介绍重定向符的基本用法和一些实用技巧&#xff0c;帮助读者更好地理解和运用这个功能。…...

Kubernetes 文档 / 概念 / 工作负载 / 工作负载管理 / Job

Kubernetes 文档 / 概念 / 工作负载 / 工作负载管理 / Job 此文档从 Kubernetes 官网摘录 中文地址 英文地址 Job 会创建一个或者多个 Pod&#xff0c;并将继续重试 Pod 的执行&#xff0c;直到指定数量的 Pod 成功终止。 随着 Pod 成功结束&#xff0c;Job 跟踪记录成功完成的…...

办公自动化-Python如何提取Word标题并保存到Excel中?

办公自动化-Python如何提取Word标题并保存到Excel中&#xff1f; 应用场景需求分析实现思路实现过程安装依赖库打开需求文件获取word中所有标题去除不需要的标题创建工作簿和工作表分割标题功能名称存入测试对象GN-TC需求标识符存入测试项标识存入需求标识符 完整源码实现效果学…...

基于Java、SpringBoot和uniapp在线考试系统安卓APP和微信小程序

摘要 基于Java、SpringBoot和uniapp的在线考试系统安卓APP微信小程序是一种结合了现代Web开发技术和移动应用技术的解决方案&#xff0c;旨在为教育机构提供一个方便、高效和灵活的在线考试平台。该系统采用Java语言进行后端开发&#xff0c;使用SpringBoot框架简化企业级应用…...

抖音a-bogus加密解析(三)

要补的环境我给提示&#xff0c;大家自行操作&#xff0c;出了问题就是因为缺环境&#xff0c;没补好 window global; // reading _u未定义 window.requestAnimationFrame function () {} // XMLHttpRequest 未定义 window.XMLHttpRequest function () {} window.onwheelx …...

IS-IS DIS

原理概述 OSPF 协议支持4种网络类型&#xff0c; IS-IS 协议只支持两种网络类型&#xff0c;即广播网络和点到点网络。与 OSPF 协议相同&#xff0c; IS-IS 协议在广播网络中会将网络视为一个伪节点( Pseudonode &#xff0c;简称 PSN )&#xff0c;并选举出一台 DIS ( Designa…...

random和range

含义&#xff1a; random(1&#xff0c;10) 不包含10&#xff0c;用于生成随机数。它可以生成浮点数或整数&#xff0c;取决于具体的使用方式。 range(0&#xff0c;1) 不包含1&#xff0c;用于生成一个整数序列。它可以生成一个指定范围内的连续整数序列。 区别在于&#x…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...