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

每日OJ_牛客_DP44兑换零钱_C++_Java

news 来源：原创 2025/6/8 5:11:32

牛客_DP44兑换零钱

题目解析

C++代码

Java代码

牛客_DP44兑换零钱

兑换零钱_牛客题霸_牛客网

描述：

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 0≤n≤10000 ，数组中每个数字都满足 0<val≤10000，0≤aim≤5000

要求：时间复杂度 O(n×aim)O(n×aim) ，空间复杂度 O(aim)O(aim)。

输入描述：

第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。

第二行给定 n 个正整数表示 arr 数组中的所有元素

输出描述：

输出组成 aim 的最少货币数

题目解析

完全背包问题且要把背包装满，返回物品的最少个数（返回最少个数初始化为一个极大值，返回最大价值初始化为一个极小值。

C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;//二维优化成一维：
int main()
{int n = 0, aim = 0;cin >> n >> aim;vector<int> arr(n + 1);for(int i = 1; i <= n; ++i){cin >> arr[i];}vector<int> dp(aim + 1, INF);dp[0] = 0;for(int i = 1; i <= n; ++i){for(int j = arr[i]; j <= aim; ++j){dp[j] = min(dp[j], dp[j - arr[i]] + 1); // 选}}cout << (dp[aim] == INF ? -1 : dp[aim]);return 0;
}//原二维代码：
// int main()
// {
//     int n = 0, aim = 0;
//     cin >> n >> aim;
//     vector<int> arr(n + 1);
//     for(int i = 1; i <= n; ++i)
//     {
//         cin >> arr[i];
//     }
//     vector<vector<int>> dp(n + 1, vector<int>(aim + 1, INF));
//     dp[0][0] = 0;
//     for(int i = 1; i <= n; ++i)
//     {
//         for(int j = 0; j <= aim; ++j)
//         {
//             dp[i][j] = dp[i - 1][j]; // 不选
//             if(j >= arr[i])
//                 dp[i][j] = min(dp[i][j], dp[i][j - arr[i]] + 1); // 选
//         }
//     }
//     cout << (dp[n][aim] == INF ? -1 : dp[n][aim]);
//     return 0;
// }//贪心错解代码
// int main()
// {
//     int n = 0, aim = 0;
//     cin >> n >> aim;
//     vector<int> arr(n);
//     for(int i = 0; i < n; ++i)
//     {
//         cin >> arr[i];
//     }
//     sort(arr.begin(), arr.end());//     int res = 0;
//     int pos = arr.size() - 1;
//     while(aim > 0)
//     {
//         while(pos >= 0 && aim < arr[pos])
//         {
//             --pos;
//         }
//         if(pos == -1)
//         {
//             cout << -1;
//             return 0;
//         }//         res += aim / arr[pos];
//         aim %= arr[pos];
//     }
//     cout << res;
//     return 0;
// }

Java代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), aim = in.nextInt();int[] arr = new int[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}int[] dp = new int[aim + 1];for(int i = 0; i <= aim; i++){dp[i] = 0x3f3f3f3f;}dp[0] = 0;for{for(int j = arr[i]; j <= aim; j++){dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);}}if(dp[aim] >= 0x3f3f3f3f) System.out.println(-1);else System.out.println(dp[aim]);}
}

每日OJ_牛客_DP44兑换零钱_C++_Java

目录牛客_DP44兑换零钱题目解析 C代码 Java代码牛客_DP44兑换零钱兑换零钱_牛客题霸_牛客网描述： 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个a…...

编程日记 2025/5/30 3:46:07

目录 1. ls指令2. pwd3. whoami指令4. cd指令5. clear指令6. touch指令7. mkdir指令8. rm指令9. man指令10. cp指令11. mv指令12. cat指令13. tac指令14. more指令15. less指令16. head指令17. tail指令18. date指令19. cal指令20. find指令21. which指令22. alias指令23. grep…...

编程日记 2025/6/2 17:20:00

VOSK实现【离线中文语音】识别

Vosk是一款开源的离线语音识别工具包，具有以下功能： 多语言支持：能够对20多种语言和方言进行语音识别，如中文、英语、德语、法语、西班牙语等，可满足不同用户的语言需求。模型轻量化：每种语言的模型大小仅…...

编程日记 2025/6/2 14:38:38

Qt 控件与布局管理

1. Qt 控件的父子继承关系在 Qt 中，继承自 QWidget 的类，通常会在构造函数中接收一个 parent 参数。这个参数用于指定当前空间的父控件，从而建立控件间的父子关系。当一个控件被设置为另一控件的子控件时，它会自动成为该父控…...

编程日记 2025/6/3 21:45:51

Checkbutton组件

在这个案例中，我们将添加三个复选框（Checkbutton）组件，每个组件都有不同的初始状态。准备就绪本文案例是在上一篇《Combobox组件》上的扩展，你可以从这里下载其中的代码。如何操作我们正在创建三个状态不同的复选框组件。第一个组件是禁用状态，并且其中有一个勾…...

编程日记 2025/6/3 17:50:51

Markdown Viewer 浏览器, vscode

使用VS Code插件打造完美的MarkDown编辑器（插件安装、插件配置、markdown语法）_vscode markdown-CSDN博客右键 .md 文件，选择打开方式 （安装一些markdown的插件) vscode如何预览markdown文件 | Fromidea GitCode - 全球开发者…...

编程日记 2025/6/3 22:14:25

【QNX】QNX侧查看CPU的信息

目录一工具 ① top ▲ 使用top查看CPU信息 ▲ 输出 ② hogs ▲ 使用hogs查看CPU信息 ▲ 输出 ③ pidin ▲ 使用pidin查看CPU信息 ▲ 输出二对比在QNX实时操作系统中，可查看CPU信息的方法有top、hogs以及pidin。一工具 ① top top命令不仅能够显…...

编程日记 2025/6/1 3:10:35

Android中关于View的几种属性赋值方式

我们以给TextView组件设置颜色属性展开讲解 1、xml中直接定义（设定TextView为黑色） 2、xml 中引用style（设定TextView为蓝色） 3、在theme 中直接定义（设定TextView紫色） 4、在主题中添加对样式资源的引用…...

编程日记 2025/6/1 19:59:14

JavaScript网页基于tesseract.js提取图片中的文字，识别车牌，识别快递单号等

Tesseract是我们的老盆友了，以前写过基于JavaCV版本的Tesseract字符识别，现在tesseract终于可以在网页上面用了（tesseract.js），让我们一起来试试效果。注意：本章使用Vue模块化调用tesseract.js方式&#x…...

编程日记 2025/6/2 2:56:57

智慧金融合集：财税资金数据管理一体化大屏

随着科技的快速进步和数字化转型的加速，金融、税务等机构和企业面临的数据量呈现出爆炸式增长。传统的数据分析方法早已无法胜任现代业务的需求。为此，许多机构开始尝试创新的软件工具来更好的管理繁琐的数据。通过图扑软件的数据可视化大屏&#xff0c…...

编程日记 2025/6/4 10:34:14

Android SystemUI——最近任务应用列表（十七）

对于最近任务应用列表来说，在 Android 原生 SystemUI 中是一个单独的组件。 <string-array name="config_systemUIServiceComponents" translatable="false">……<item>com.android.systemui.recents.Recents</item> </string-arra…...

编程日记 2025/6/3 16:34:04

工业相机 SDK 二次开发-Halcon 插件

本文介绍了 Halcon 连接相机时插件的使用。通过本套插件可连接海康的工业相机。一. 环境配置 1. 拷贝动态库在用户安装 MVS 目录下按照如下路径 Development\ThirdPartyPlatformAdapter 找到目录为 HalconHDevelop 的文件夹，根据 Halcon 版本找到对…...

编程日记 2025/6/3 2:26:05

AI Agent：数字文明的暗物质，如何悄然改变我们的世界？

AI Agent：数字文明的暗物质，如何悄然改变我们的世界？ 引言在人类文明的漫长黑夜中，人工智能（Artificial Intelligence, AI）如同第一缕曙光，正在撕裂数字与现实的边界。这是一个技术奇点临近的…...

编程日记 2025/5/29 11:14:18

vscode 自用插件

vscode按住ctrl鼠标左键无法跟踪跳转方法名，装这些插件就可以 vscode-elm-jump:常规的代码跳转定义 Vue CSS Peek:跳转css定义 vue-helper:变量函数只跳转定义 Vetur 代码提示 Baidu Comate 自动帮你写console.log Turbo Console Log: ctrl alt l 选中变量之后&am…...

编程日记 2025/6/3 5:04:12

Ragas-RAG能力评测

Ragas是一个框架，它可以帮助你从不同的方面评估你的问答（QA）流程。它为你提供了一些指标来评估你的问答系统的不同方面，具体包括： 评估检索（context）的指标：提供了上下文相关性&…...

编程日记 2025/6/3 16:25:17

【PCL】Segmentation 模块—— 条件欧几里得聚类（Conditional Euclidean Clustering）

1、简介 1.1 条件欧几里得聚类（Conditional Euclidean Clustering） 本文介绍了如何使用 pcl::ConditionalEuclideanClustering 类：这是一种基于欧几里得距离和用户自定义条件的点云聚类分割算法。该类使用了与欧几里得聚类提取(Euclidean…...

编程日记 2025/6/3 23:23:31

#HarmonyOS篇：build-profile.json5里面配置productsoh-package.json5里面dependencies依赖引入

oh-package.json5 用于描述包名、版本、入口文件和依赖项等信息。 {"license": "","devDependencies": {},"author": "","name": "entry","description": "Please describe the basic…...

编程日记 2025/6/2 6:54:52

《探秘：人工智能如何为鸿蒙Next元宇宙网络传输与延迟问题破局》

在元宇宙的宏大愿景中，流畅的网络传输和低延迟是保障用户沉浸式体验的关键。鸿蒙Next结合人工智能技术，为解决这些问题提供了一系列创新思路和方法。智能网络监测与预测人工智能可以实时监测鸿蒙Next元宇宙中的网络状况，包括带宽、延迟、…...

编程日记 2025/6/2 17:17:46

java中的泛型

文章目录 java中的泛型泛型的使用1 快速入门2 泛型的介绍（1）使用泛型的好处（2）泛型的理解（3）泛型的语法（4）泛型使用的注意事项 3 自定义泛型（1）自定义泛型类&…...

编程日记 2025/6/2 6:54:35

PCF8563一款工业级、低功耗多功能时钟/日历芯片

PCF8563是PHILIPS（现NXP）公司生产的一款工业级、内含I2C总线接口功能的低功耗多功能时钟/日历芯片。以下是对该芯片的详细介绍： 一、主要特性低功耗：典型值为0.25μA（VDD3.0V，Tamb25℃）。宽电…...

编程日记 2025/6/1 22:10:32

Servlet快速入门

Servlet 由于目前主流使用SpringBoot进行开发Servlet可以说是时代的眼泪，这篇文章主要介绍我基于SpringBoot对应Servlet的浅薄认知，有利于更好的理解前端界面和java服务器的数据交换过程快速入门我比较推荐这篇文章来对Servlet有一个大概的了解都2…...

编程日记 2025/6/3 2:32:10

C语言初阶牛客网刷题——JZ17 打印从1到最大的n位数【难度：入门】

1.题目描述牛客网OJ题链接题目描述： 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。用返回一个整数列表来代替打印n 为正整数，0 < n < 5 示例1 输入&…...

编程日记 2025/6/3 5:03:29

【组件分享】商品列表组件-最佳实践

商品列表组件商品列表组件用于展示商品信息列表，支持多种布局方式和自定义配置。基础用法 <template><ProGoodsList :goods-list"goodsList" :layout"layout" item-click"handleItemClick" /> </template>&l…...

编程日记 2025/5/30 15:18:53

【JAVA】BOSS系统发版艺术：构建高效、优雅的微服务部署策略

在现代软件开发领域，微服务架构与容器化部署已迅速成为行业新趋势。微服务架构通过将应用拆分成多个小型、自治的服务单元，每个服务承担某项特定的业务功能。而容器化部署则以其轻量级和高度可移植的特性，为这些微服务的有效打包、分发和运行…...

编程日记 2025/6/2 18:02:39

React的响应式

在 React 中，useState 是一个 Hook，用于在函数组件中定义和管理状态。 setCount 是由 useState 返回的第二个值，用于更新状态并触发组件重新渲染。它的本质是一个状态更新函数，背后是 React 的状态管理和调度机制。下面是对 setCo…...

编程日记 2025/6/3 13:03:46

deep face cam 部署报错解决

这里写自定义目录标题使用conda创建py3.9环境使用按照readme.txt安装所有依赖后遇到的报错2.最后一个模块insightface安装报错3.运行run.py又报错原因：解决方法：4.缺少模块解决方法：pip命令安装5.AttributeError: NoneType object has no attribute configure解决方法：安装…...

编程日记 2025/6/4 14:21:20

图像处理基础(4)：高斯滤波器详解

本文主要介绍了高斯滤波器的原理及其实现过程高斯滤波器是一种线性滤波器，能够有效的抑制噪声，平滑图像。其作用原理和均值滤波器类似，都是取滤波器窗口内的像素的均值作为输出。其窗口模板的系数和均值滤波器不同，均值滤波器的…...

编程日记 2025/6/2 4:33:10

outlook附件限制最大5m如何解决

Outlook 附件大小限制为 5MB，通常由邮件服务器（如 Exchange、Office 365、Gmail 等）或本地 Outlook 配置决定。可以采取以下几种方法来解决该限制问题： 解决方案 1：调整服务器端限制（管理员权限&#xff09…...

编程日记 2025/6/3 16:16:01

Word常见问题：嵌入图片无法显示完整

场景：在Word中，嵌入式图片显示不全，一部分图片在文字下方。如： 问题原因：因段落行距导致方法一快捷方式选中图片，通过"ctrl1"快捷调整为1倍行距方法二通过工具栏调整选中图片&#xff0…...

编程日记 2025/6/2 19:31:41

【面试题】java基础概念

以下是关于这道面试题的回答，包括JDK中一些相关概念的区别以及JIT的原理： JDK中相关概念区别 JDK、JRE和JVM JDK（Java Development Kit）：是Java开发工具包，它包含了JRE和一系列开发工具。JDK提供了编译、…...

编程日记 2025/6/2 6:21:11

WebSocket实现私聊私信功能

目录后端pom.xmlConfig配置类Controller类DTO 前端安装相关依赖websocketService.js接口javascripthtmlCSS 效果展示简单测试连接： 报错解决方法1、vue3 使用SockJS报错 ReferenceError: global is not defined 后面将继续完善，待更新... 后端 pom.xml…...

编程日记 2025/6/2 6:34:10

进程的哪些内存类型容易引起内存泄漏

相信你在平时的工作中，应该遇到过下面这些场景： 伴随着服务器中的后台任务持续地运行，系统中可用内存越来越少； 应用程序正在运行时忽然被 OOM kill 掉了； 进程看起来没有消耗多少内存，但是系统内存就是不够…...

编程日记 2025/5/31 1:54:07

用着很顺手的电脑亮度随心随意调节

一、功能介绍显示高级设置，可以调节屏幕RGB色彩。娱乐亮度，一键娱乐亮度调节。护眼亮度，保护眼睛，减少蓝光。恢复正常，一键恢复到默认模块。二、问题解答 1、亮度更改后显示器无变化！软件根本都没…...

编程日记 2025/5/30 13:44:47

图片生成Prompt编写技巧

1. 图片情绪（场景氛围） 一张图片一般都会有一个情绪基调，因为作画本质上也是在传达一些情绪，一般都会借助图片的氛围去转达。例如：比如家庭聚会一般是欢乐、喜乐融融。断壁残垣一般是悲凉。还有萧瑟、孤寂等。 2.补充细…...

编程日记 2025/5/31 9:37:25

博客之星2024年度总评选——我的年度创作回顾与总结

2024年，是我在CSDN博客上持续耕耘、不断成长的一年。在此，与大家分享一下我的年度创作回顾与总结。一、创作成长与突破在人工智能领域，技术迭代迅速，知识更新频繁。为了保持自己的竞争力，在今年，我始终…...

编程日记 2025/6/2 13:38:25

前端Vue2项目使用md编辑器

项目中有一个需求，要在前端给用户展示内容，内容有 AI 生成的，返回来的是 md 格式，所以需要给用户展示 md 格式，并且管理端也可以编辑这个 md 格式的文档。使用组件库 v-md-editor。 https://code-farmer-i.github.i…...

编程日记 2025/6/1 8:29:26

Docker核心命令与Yocto项目的高效应用

随着软件开发逐渐向分布式和容器化方向演进，Docker 已成为主流的容器化技术之一。它通过标准化的环境配置、资源隔离和高效的部署流程，大幅提高了开发和构建效率。Yocto 项目作为嵌入式 Linux 系统构建工具，与 Docker 的结合进一步增强了开发…...

编程日记 2025/5/30 6:49:04

kong 网关和spring cloud gateway网关性能测试对比

该测试只是简单在同一台机器设备对spring cloud gateway网关和kong网关进行对比，受限于笔者所拥有的资源，此处仅做简单评测。一、使用spring boot 的auth-service作为服务提供者该服务提供了一个/health接口，接口返回"OK"&…...

编程日记 2025/6/1 16:29:05

DDoS攻击防护能力测试：Python版脚本

引言在互联网服务日益复杂和流量持续增长的今天，确保服务器能够应对高并发请求并具备良好的抗DDoS攻击的能力至关重要。声明以下代码仅在合法的前提下使用。工具设计原理脚本的核心在于它能够创建多个线程来并发执行不同的攻击方法，从而实现对目标…...

编程日记 2025/5/30 16:09:41

白玉微瑕：闲谈 SwiftUI 过渡（Transition）动画的“口是心非”（下）

概述秃头小码农们都知道，SwiftUI 不仅仅是一个静态 UI 构建框架那么简单，辅以海量默认或自定义的动画和过渡（Transition）特效，我们可以将 App 界面的绚丽升华到极致。不过，目前 SwiftUI 中的过渡&#x…...

编程日记 2025/5/30 5:04:38

5.4 解锁 OpenAI - Translator：模块设计，构建翻译系统的 “基石”

OpenAI-Translator 模块设计 OpenAI-Translator 作为一款基于 OpenAI GPT 模型的智能翻译助手，其模块设计至关重要。为了保证翻译的高效性、准确性与可扩展性，系统需要一个结构清晰、功能强大的模块化设计。本文将对 OpenAI-Translator 的各个模块进行详细解析，涵盖其核心功…...

编程日记 2025/6/2 17:17:44

数据分析变异系数

目录变异系数的应用场景包括： 特点： 注意事项： np.nanvar——方差，np.sanstd标准差简单来讲就是平均值/标准差变异系数（Coefficient of Variation, CV）是一种相对量的变异指标，常用于衡…...

编程日记 2025/6/3 13:57:55

C语言——编译与链接

目录前言一程序的两种环境 1翻译环境 2执行环境二预处理 1预处理符号 2#define 2.1#define 定义标识符 2.2#define 定义宏 2.2.1#和## 2.3带副作用的宏参数 2.4宏和函数的比较 2.5命名约定 3#undef 4命令行定义 5条件编译 5.1单分支 5.2多分支 5.3判断是…...

编程日记 2025/6/4 12:21:01

NewStar CTF week1 web wp

谢谢皮蛋做这题之前需要先去学习一些数据库的知识 1 order by 2 1可以理解为输入的id，是一个占位符，按第二列排序用来测试列数，如果没有两列则会报错-1 union select 1,2 -1同样是占位符，union的作用是将注入语句合并到原始语句…...

编程日记 2025/6/2 17:00:27

Android BitmapShader简洁实现马赛克，Kotlin（一）

Android BitmapShader简洁实现马赛克，Kotlin（一） 这一篇， Android使用PorterDuffXfermode模式PorterDuff.Mode.SRC_OUT橡皮擦实现马赛克效果，Kotlin（3）-CSDN博客基于PorterDuffXfermode实现马…...

编程日记 2025/6/3 16:52:10

NavVis手持激光扫描帮助舍弗勒快速打造“数字孪生”工厂-沪敖3D

在全球拥有近100家工厂的舍弗勒，从2016年开启数字化运营进程，而当前制造、库存、劳动力和物流的数字化，已无法支持其进一步简化工作流程，亟需数字化物理制造环境，打造“数字孪生”工厂。 NavVis为其提供NavVis VLX 3…...

编程日记 2025/6/3 8:04:53

web服务器网站部署的架构

WEB服务器工作原理 Web web是WWW(World Wide Web)的简称，基本原理是：请求(客户端)与响应(服务器端)原理，由遍布在互联网中的Web服务器和安装了Web浏览器的计算机组成客户端发出请求的方式：地址栏请求、超链接请求、表单请求 …...

编程日记 2025/6/4 15:35:35

ecovadis验厂相关要求

EcoVadis验厂的相关要求主要包括以下几个方面： 一、企业基本资质要求合法注册与运营：企业必须是合法注册并运营的法人实体，具备合法的经营资质，如营业执照、税务登记证等。无严重违法记录：在过去三年内，…...

编程日记 2025/6/4 16:18:25

SSM开发(一)JAVA,javaEE,spring,springmvc,springboot,SSM,SSH等几个概念区别

目录 JAVA 框架 javaEE spring springmvc springboot SSM SSH maven JAVA 一种面向对象、高级编程语言，Python也是高级编程语言；不是框架(框架：一般用于大型复杂需求项目，用于快速开发)具有三大特性，所谓Jav…...

编程日记 2025/5/30 20:28:36

Spring Boot中选择性加载Bean的几种方式

说明：用过Spring框架的都知道其自动装配的特性，本文介绍几种选择性加载Bean的方式。Spring自动装配参考以下两篇文章： 基于SpringBoot的三层架构开发&统一响应结果 SpringBoot自动装配原理简单分析 ConditionalOnProperty Conditiona…...

编程日记 2025/6/4 11:02:25

牛客_DP44兑换零钱

题目解析

C++代码

Java代码

相关文章：