每日一题 518零钱兑换2(完全背包)
题目
给你一个整数数组 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
题解
记忆化搜索
class Solution {private int[] coins;private int[][] cache;public int change(int amount, int[] coins) {this.coins = coins;int n = coins.length;cache = new int[n][amount + 1];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1, amount);}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 1 : 0;}if (cache[i][c] != -1) {return cache[i][c];}if (c < coins[i]) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = dfs(i - 1, c) + dfs(i, c - coins[i]);}
}
1:1递推
class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[][] f = new int[n + 1][amount + 1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= amount; c++) {if (c < coins[i]) {f[i + 1][c] = f[i][c];} else {f[i + 1][c] = f[i][c] + f[i + 1][c - coins[i]]; }}}return f[n][amount];}
}
空间优化
class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[] f = new int[amount + 1];f[0] = 1;for (int x : coins) {for (int c = x; c <= amount; c++) {f[c] += f[c - x];}}return f[amount];}
}
相关文章:
每日一题 518零钱兑换2(完全背包)
题目 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整…...
Linux shell编程学习笔记8:使用字符串
一、前言 字符串是大多数编程语言中最常用最有用的数据类型,这在Linux shell编程中也不例外。 本文讨论了Linux Shell编程中的字符串的三种定义方式的差别,以及字符串拼接、取字符串长度、提取字符串、查找子字符串等常用字符串操作,,以及反…...
【Spring笔记03】Spring依赖注入各种数据类型
这篇文章,详细介绍一下Spring框架中如何注入各种数据类型,包含:注入基本数据类型、数组、集合、Map映射、Property属性、注入空字符串、注入null值、注入特殊字符等内容,以及如何使用命名空间进行依赖注入。 目录 一、注入各种数据…...
2023计算机保研——双非上岸酒吧舞
我大概是从22年10月份开始写博客的,当时因为本校专业的培养方案的原因,课程很多,有些知识纸质记录很不方便,于是选择了打破了自己的成见使用博客来记录学习生活。对于我个人而言,保研生活在前一大半过程中都比较艰难&a…...
《计算机视觉中的多视图几何》笔记(13)
13 Scene planes and homographies 本章主要讲述两个摄像机和一个世界平面之间的射影几何关系。 我们假设空间有一平面 π \pi π,平面上的一点为 x π x_{\pi} xπ。 x π x_{\pi} xπ分别在两幅图像 P , P ′ P, P P,P′上形成了 x , x ′ x, x x,x′。 那…...
H5移动端购物商城系统源码 小型商城全新简洁风格全新UI 支持易支付接口
一款比较简单的 H5 移动端购物商城系统源码,比较适合单品商城、小型商城使用。带有易支付接口。 源码下载:https://download.csdn.net/download/m0_66047725/88391704 源码下载2:评论留言或私信留言...
全志ARM926 Melis2.0系统的开发指引⑤
全志ARM926 Melis2.0系统的开发指引⑤ 编写目的8. 固件修改工具(ImageModify)使用8.1.界面说明8.2.操作步骤8.2.1. 配置平台8.2.2. 选择固件8.2.3. 选择要替换的文件8.2.4. 替换文件8.2.5. 保存固件 8.3.注意事项8.4.增加固件修改权限设置8.4.1. 概述8.4.2. 操作说明8.4.2.1.打…...
【AI视野·今日Robot 机器人论文速览 第四十七期】Wed, 4 Oct 2023
AI视野今日CS.Robotics 机器人学论文速览 Wed, 4 Oct 2023 Totally 40 papers 👉上期速览✈更多精彩请移步主页 Interesting: 📚基于神经网络的多模态触觉感知, classification, position, posture, and force of the grasped object多模态形象的解耦(f…...
GPX可视化工具 GPX航迹预览工具
背景 当我们收到别人分享的航迹文档,即gpx文档时,如何快速的进行浏览呢?我们可以使用GIS软件来打开gpx文档并显示gpx中所记录的航迹,例如常用的GIS软件有googleEarth, Basecamp, GPXsee, GPX E…...
学信息系统项目管理师第4版系列18_采购管理
1. 协议 1.1. 合同 1.1.1. 国际合作的项目经理应牢记,无论合同规定如何详尽,文化和当地法律对合同及其可执行性均有影响 1.2. 服务水平协议(SLA) 1.3. 谅解备忘录 1.4. 协议备忘录(MOA) 1.5. 订购单 …...
标准化数据模型
标准化数据模型 标准化被定义为减少或消除数据集中冗余的过程。 它已成为关系数据库中数据建模的事实上的方法,很大程度上是由于这些系统最初设计时所围绕的底层资源限制:缓慢的磁盘和昂贵的 RAM。更少的数据冗余/重复意味着更有效地从磁盘读取数据并占…...
linux平台源码编译ffmpeg
目录 编译平台 编译步骤 编译平台 中标麒麟 编译步骤 1 从Download FFmpeg 下载源码,我选中了4.2.9版 2 解压 3 在解压后的目录下输入 ./configure --enable-shared --prefix/usr/local/ffmpeg 4 make 5 sudo make install 6 ffmpeg的头文件、可执行程…...
Vue中如何进行拖拽与排序功能实现
在Vue中实现拖拽与排序功能 在Web应用程序中,实现拖拽和排序功能是非常常见的需求,特别是在管理界面、任务列表和图形用户界面等方面。Vue.js作为一个流行的JavaScript框架,提供了许多工具和库来简化拖拽和排序功能的实现。本文将介绍如何使…...
新款UI动态壁纸头像潮图小程序源码
新款UI动态壁纸头像潮图小程序源码,不需要域名服务器,直接添加合法域名,上传发布就能使用。 可以对接开通流量主,个人也能运营,不需要服务器源码完整。整合头像,动态壁纸,文案功能齐全。 源码…...
Python逐日填补Excel中的日期并用0值填充缺失日期的数据
本文介绍基于Python语言,读取一个不同的列表示不同的日期的.csv格式文件,将其中缺失的日期数值加以填补;并用0值对这些缺失日期对应的数据加以填充的方法。 首先,我们明确一下本文的需求。现在有一个.csv格式文件,其第…...
【C语言经典100例题-70】求一个字符串的长度(指针)
代码 使用指针来遍历字符串,直到遇到字符串结尾的空字符\0为止,统计字符数量即为字符串长度。 #include<stdio.h> #define n 20 int getlength(char *a) {int len 0;while(*a!\0){len;a;}return len; } int main() {char *arr[n] { 0 };int l…...
十天学完基础数据结构-第八天(哈希表(Hash Table))
哈希表的基本概念 哈希表是一种数据结构,用于存储键值对。它的核心思想是将键通过哈希函数转化为索引,然后将值存储在该索引位置的数据结构中。 哈希函数的作用 哈希函数是哈希表的关键部分。它将输入(键)映射到哈希表的索引位…...
flink集群部署
虚拟机配置 bigdata-hmaster 192.168.135.112 4核心 32GB bigdata-hnode1 192.168.135.113 4核心 16GB bigdata-hnode2 192.168.135.114 4核心 16GB 安装包:https://dlcdn.apache.org/flink/flink-1.17.1/flink-1.17.1-bin-scala_2.12.tgz 放到/usr/lcoal/lib目录…...
2.证明 非单一点 Oct.2023
目录 原题解引申出的编程问题非单一点题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 题解题目正解 原题 已知等边 Δ P 0 P 1 P 2 \Delta P_0P_1P_2 ΔP0P1P2,它的外接圆是 O O O,设 O O O的半径是 R R R。同时,设 Δ …...
常见的软件脱壳思路
单步跟踪法 1.本方法采用OD载入。 2.跟踪F8,实现向下的跳。 3.遇到程序回跳按F4。 4.绿色线条表示跳转没实现,不用理会,红色线条表示跳转已经实现! 5.刚载入程序有一个CALL的,我们就F7跟进去,不然程序很容…...
极客专属:OpenClaw+百川2-13B打造个人CLI智能助手
极客专属:OpenClaw百川2-13B打造个人CLI智能助手 1. 为什么开发者需要命令行智能助手 作为一个长期与终端打交道的开发者,我每天要重复执行大量机械操作:查看日志、运行测试、整理结果。这些工作虽然简单,却极其消耗精力。直到我…...
RAG深度解析一:从参数化知识到检索增强的范式重构
【内容定位】深度技术原理【文章日期】2026-03-27【场景引入】进入2026年3月,一场围绕大语言模型“可信性”的讨论在技术社区再度升温。开发者们早已不再争论模型参数量,而是转向一个更实际的问题:如何让动辄千亿参数的大模型,在回…...
mmsegmentation训练策略调优全攻略:从学习率预热到迭代次数计算
mmsegmentation训练策略调优实战:从参数配置到显存优化 在图像分割领域,mmsegmentation框架因其模块化设计和丰富的预训练模型而广受欢迎。但真正决定模型性能上限的,往往是那些容易被忽视的训练策略细节。本文将带您深入AdamW优化器的参数微…...
天津专业的阀门厂排名
在天津,阀门行业发展态势良好,众多阀门厂各有特色与优势。中国通用机械工业协会最新发布的《2026年阀门行业高质量发展白皮书》显示,天津的阀门产业在技术创新、产品质量和市场份额等方面都有不错的表现。下面为大家介绍几家天津比较知名的阀…...
Linux DRM子系统深度解析:如何为240x240 SPI屏编写自定义KMS驱动?
Linux DRM子系统实战:为240x240 SPI屏构建原子化KMS驱动 当一块小巧的240x240 SPI屏幕遇上Linux DRM显示框架,开发者面临的不仅是硬件接口的适配,更是一场关于现代显示架构的深度对话。本文将带您穿透DRM子系统的抽象层,从KMS核心…...
GIS开发必备:5分钟搞定EPSG3857转WGS84坐标转换(附proj4.js完整代码)
GIS开发实战:从原理到代码实现EPSG3857与WGS84的高效坐标转换 刚接触WebGIS开发的工程师们,常常会被各种坐标系搞得晕头转向。为什么高德地图上显示的位置和GPS设备采集的数据对不上?为什么Leaflet、OpenLayers这些库加载的瓦片地图坐标数值大…...
别再到处找模板了!我用这套软著申请材料(含用户手册+源代码模板)两个月搞定
两个月高效拿下软著:零基础开发者的材料准备实战指南 第一次提交软著申请时,我盯着官网模糊的材料要求整整发呆了半小时——"用户手册需图文并茂"到底要多详细?"源代码前30页后30页"该怎么截取?连续三个晚上搜…...
通义千问3-Reranker-0.6B优化升级:调整批处理大小和自定义指令,性能再提升5%
通义千问3-Reranker-0.6B优化升级:调整批处理大小和自定义指令,性能再提升5% 1. 为什么需要优化重排序模型性能? 在信息检索和问答系统中,重排序模型扮演着至关重要的角色。它负责对初步检索得到的文档进行二次排序,…...
多模态扩展:OpenClaw+GLM-4.7-Flash处理图片信息
多模态扩展:OpenClawGLM-4.7-Flash处理图片信息 1. 为什么需要多模态能力 上周我在整理产品截图时遇到一个典型问题:需要从200多张UI截图中提取所有按钮文字和位置信息。手动操作不仅耗时,还容易遗漏细节。这让我开始思考——能否让OpenCla…...
网络工程师-核心考点:计算机硬件基础全解析
一、引言计算机硬件基础是软考网络工程师考试的前置知识点,占选择题分值约 3-5 分,是理解网络设备(路由器、交换机、服务器)硬件架构的底层基础。本知识点体系起源于 1945 年冯・诺依曼提出的存储程序思想,历经 70 余年…...
