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

Leecode刷题C语言之购买水果需要的最小金币数

news 来源：原创 2025/5/24 11:37:47

执行结果:通过

执行用时和内存消耗如下：

 

 

 

int dp(int* prices, int pricesSize, int index, int* memo) {if (2 * index + 2 >= pricesSize) {return prices[index];}if (memo[index] == -1) {int minValue = INT_MAX;for (int i = index + 1; i <= 2 * index + 2; i++) {minValue = fmin(minValue, dp(prices, pricesSize, i, memo));}memo[index] = prices[index] + minValue;}return memo[index];
}int minimumCoins(int* prices, int pricesSize) {int *memo = (int*)malloc(pricesSize * sizeof(int));for (int i = 0; i < pricesSize; i++) {memo[i] = -1;}return dp(prices, pricesSize, 0, memo);
}

解题思路：

这段代码的目的是解决一个特定类型的动态规划问题，其中涉及到在给定的价格数组 prices 中选择若干元素，使得所选元素的总和最小，但有一个特殊的约束条件：如果你选择了价格数组中的第 i 个元素，那么你只能选择第 i+1, i+2, ..., 或 2*i+2 个元素作为下一个要选择的元素（如果存在的话）。下面详细解释这段代码的思路：

  1. 定义问题：
    • 输入：一个整数数组 prices 和数组的大小 pricesSize。
    • 输出：在满足上述约束条件的前提下，从 prices 中选择若干元素所能得到的最小总和。
  2. 动态规划（DP）思路：
    • 使用一个递归函数 dp(prices, pricesSize, index, memo) 来计算从 index 位置开始选择元素的最小总和。
    • memo 数组用于存储中间结果，以避免重复计算。memo[i] 存储的是从第 i 个位置开始的最小总和。
  3. 递归函数 dp 的逻辑：
    • 基本情况：如果当前位置 index 之后的可选范围超出了数组边界（即 2 * index + 2 >= pricesSize），则直接返回当前位置的价格 prices[index]，因为没有后续元素可选。
    • 记忆化：检查 memo[index] 是否已经被计算过（即不等于 -1）。如果是，则直接返回 memo[index]。
    • 递归计算：如果 memo[index] 未被计算，遍历从 index + 1 到 2 * index + 2 的所有可能下一个选择位置 i，对每个位置递归调用 dp 函数，找到这些选择中的最小值 minValue。
    • 更新 memo：将当前位置 index 的最小总和更新为 prices[index] + minValue，并存储在 memo[index] 中。
    • 返回结果：返回 memo[index]。
  4. 主函数 minimumCoins：
    • 分配内存并初始化 memo 数组，所有元素初始化为 -1，表示尚未计算。
    • 从位置 0 开始调用递归函数 dp，并返回其结果作为最终的最小总和。
  5. 内存管理：
    • 在实际使用中，这段代码应该在适当的地方释放 memo 数组分配的内存，以避免内存泄漏。不过，在提供的代码片段中，没有显示释放内存的操作。

相关文章：

Leecode刷题C语言之购买水果需要的最小金币数

执行结果:通过 执行用时和内存消耗如下&#xff1a; int dp(int* prices, int pricesSize, int index, int* memo) {if (2 * index 2 > pricesSize) {return prices[index];}if (memo[index] -1) {int minValue INT_MAX;for (int i index 1; i < 2 * index 2; i) …...

编程日记 2025/5/24 11:37:47

【27】Word：徐雅雯-艺术史文章❗

目录 题目​ NO1.2 NO3 NO4 NO5 NO6.7 NO8.9 NO10.11 注意&#xff1a;修改样式的字体颜色/字号&#xff0c;若中英文一致&#xff0c;选择所有脚本。格式相似的文本→检查多选/漏选格式刷F4重复上一步操作请❗每一步检查和保存 题目 NO1.2 F12另存为布局→行号布局…...

编程日记 2025/5/23 0:30:38

MySQL日志详解——日志分类、二进制日志bin log、回滚日志undo log、重做日志redo log

文章目录 一、前言1.1 MySQL体系结构1.2 MySQL日志分类1.3 其他几种日志1.3.1 查询日志1.3.2 慢查询日志1.3.3 错误日志 二、bin log 二进制日志2.1 bin log简介2.2 binlog日志格式2.3 日志删除2.4 写入/刷盘机制 三、undo log 回滚日志3.1 undo log简介3.2 隐藏字段 —— 事务…...

编程日记 2025/5/24 11:29:01

数字MIC PDM接口

在音频采样中&#xff0c;我们经常会用到PCM&#xff0c;PDM这种方式&#xff0c;它们之间也是有一些区别的。 &#xff11;&#xff1a;PDM 工作原理&#xff1a; PDM使用远高于PCM采样率的时钟采样调制模拟分量&#xff0c;每次采样结果只有1位输出&#xff08;0或1&…...

编程日记 2025/5/24 10:50:40

dfs专题五：FloodFill算法

1.图像渲染 link:733. 图像渲染 - 力扣&#xff08;LeetCode&#xff09; code class Solution { public:int prev;vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if(image[sr][sc] color) return …...

编程日记 2025/5/24 11:30:35

笔试-二维数组

应用 快递业务有N个站点&#xff0c;1<N<10000&#xff1b;站点0、站点1可达&#xff0c;记作0-1&#xff1b;如果0-1、1-2&#xff0c;则站点0、站点2可达&#xff0c;记作0-2&#xff1b;s[i][j]1表示i-j可达&#xff0c;反之s[i][j]0表示i-j不可达&#xff1b;s[i][j…...

编程日记 2025/5/24 6:00:10

大模型GUI系列论文阅读 DAY2续：《一个具备规划、长上下文理解和程序合成能力的真实世界Web代理》

摘要 预训练的大语言模型&#xff08;LLMs&#xff09;近年来在自主网页自动化方面实现了更好的泛化能力和样本效率。然而&#xff0c;在真实世界的网站上&#xff0c;其性能仍然受到以下问题的影响&#xff1a;(1) 开放领域的复杂性&#xff0c;(2) 有限的上下文长度&#xff…...

编程日记 2025/5/23 0:06:29

如何提升IP地址查询数据服务的安全？

随着网络科技深入人们的生活之中&#xff0c;数据相关服务顺时代浪潮应运而生。而在数据查询相关服务之中&#xff0c;数据安全乃是重中之重。而如何部署数据查询服务安全&#xff0c;今天让我们来大致了解一下&#xff1a; 数据加密 数据加密是数据查询服务安全的核心技术之…...

编程日记 2025/5/19 1:58:24

【Leetcode】--- 接雨水

题目传送门 方法一&#xff1a; 前缀和后缀和 算法原理 需要两个数组。 第一个数组存储最左边到第 i 个位置的最大高度&#xff08;前缀最大值&#xff09; 第二个数组存储最右边到第 i 个位置的最大高度&#xff08;后缀最大值&#xff09; 最终第 i 个位置的 接水量 min&am…...

编程日记 2025/5/22 5:31:58

深入探索Math.NET：开启高效数值计算之旅

一、引言 在当今数字化时代&#xff0c;数值计算已然成为科学研究、工程设计、金融分析等众多领域的核心驱动力。从探索宇宙奥秘的物理学计算&#xff0c;到优化建筑结构的土木工程设计&#xff0c;再到预测市场趋势的金融建模&#xff0c;数值计算的身影无处不在&#xff0c;…...

编程日记 2025/5/19 6:36:56

案例研究丨浪潮云洲通过DataEase推进多维度数据可视化建设

浪潮云洲工业互联网有限公司&#xff08;以下简称为“浪潮云洲”&#xff09;成立于2018年&#xff0c;定位于工业数字基础设施建设商、具有国际影响力的工业互联网平台运营商、生产性互联网头部服务商。截至目前&#xff0c;浪潮云洲工业互联网平台连续五年入选跨行业跨领域工…...

编程日记 2025/5/24 11:27:12

Logback日志文件详细配置

完整版Logback.xml文件 放在Resources目录下即可 Mac用户更改一下日志文件存放地点即可 <FileNamePattern>/Users/***/***/tlias-%d{yyyy-MM-dd}-%i.log</FileNamePattern> <?xml version"1.0" encoding"UTF-8"?> <configurati…...

编程日记 2025/5/21 17:55:56

TDengine 与上海电气工业互联网平台完成兼容性认证

在工业数字化转型和智能化升级的浪潮中&#xff0c;企业对高效、可靠的数据管理解决方案的需求日益增长。特别是在风电智能运维、火电远程运维、机床售后服务等复杂多样的工业场景下&#xff0c;如何实现海量设备和时序数据的高效管理&#xff0c;已经成为推动行业升级的关键。…...

编程日记 2025/5/21 14:33:26

VMware虚拟机安装macOS11

1.安装虚拟机 如果尚未安装虚拟机&#xff0c;请先进行安装。地址&#xff1a;VMware17下载地址​​​​​​ 2、下载苹果镜像文件 macOS Big Sur 11.0.1 (20B29) 3、下载unlock文件&#xff08;目的是开启VMware的macOS选项功能&#xff09; https://download.csdn.net/d…...

编程日记 2025/5/19 20:54:46

PostgreSQL中级专家是什么意思？

数据库技术领域&#xff0c;PostgreSQL 作为一种广泛使用的开源关系型数据库管理系统&#xff0c;吸引了众多技术人员深入学习和研究。“PostgreSQL 中级专家” 是对掌握该数据库特定技能层次的一种描述。 知识储备 中级专家深入理解 PostgreSQL 的体系结构&#xff0c;包括进程…...

编程日记 2025/5/24 11:15:14

ubuntu20使用apt安装mysql8

目录 ubuntu20使用apt安装mysql8报错列表参考链接首先删除旧mysql 一、下载配置mysql8库索引下载apt包解压包配置更新apt库索引 二、下载安装mysql8三、启动mysql服务配置开机自启动&#xff0c;忽略 本地登录远程登录查看mysql的所有用户使用客户端远程登陆如果报错完成 参考链…...

编程日记 2025/5/22 12:47:25

FastDFS的安装及使用

分布式存储发展历程 前段时间 618 活动火热进行&#xff0c;正是购物的好时机。当我们访问这些电 商网站的时候&#xff0c;每一个商品都会有各式各样的图片展示介绍&#xff0c;这些图 片一张两张可以随便丢在服务器的某个文件夹中&#xff0c;可是电商网站如此 大体量的…...

编程日记 2025/5/19 14:44:32

二叉树（了解）c++

二叉树是一种特殊的树型结构&#xff0c;它的特点是: 每个结点至多只有2棵子树(即二叉树中不存在度大于2的结点) 并且二叉树的子树有左右之分&#xff0c;其次序不能任意颠倒&#xff0c;因此是一颗有序树 以A结点为例&#xff0c;左边的B是它的左孩子&#xff0c;右边的C是…...

编程日记 2025/5/24 10:20:13

头像生成小程序搭建（免费分享）

如下图为小程序页面的基本效果&#xff0c;下面将介绍该小程序的功能 页面template代码如下&#xff1a; <template><view class"avatar-containner"><block v-if"!showCropper"><image class"pageback" src"../../s…...

编程日记 2025/5/23 5:09:34

Alluxio 联手 Solidigm 推出针对 AI 工作负载的高级缓存解决方案

作者&#xff1a;Wayne Gao, Yi Wang, Jie Chen, Sarika Mehta Alluxio 作为全球领先的 AI 缓存解决方案供应商&#xff0c; 提供针对 GPU 驱动 AI 负载的高速缓存。其可扩展架构支持数万个节点&#xff0c;能显著降低存储带宽的消耗。Alluxio 在解决 AI 存储挑战方面的前沿技…...

编程日记 2025/5/20 10:49:31

【ComfyUI专栏】ComfyUI 部署Kolors

什么是Kolors？我相信一定会有朋友可能第一次听说这个生图的模型，开始我也很难想象，这竟然是快手推出的可灵AI的项目，我们可以直接利用模型来生成图片和视频。 大家可以通过直接访问可灵AI的网址获取到可灵的项目，但是对于我们来说我们需要基于ComfyUI来生成必要的图片和视…...

编程日记 2025/5/21 6:48:32

HBase的原理

一、什么是HBase HBase是一个分布式&#xff0c;版本化&#xff0c;面向列的数据库&#xff0c;依赖Hadoop和Zookeeper &#xff08;1&#xff09;HBase的优点 提供高可靠性、高性能、列存储、可伸缩、实时读写的数据库系统 (2) HBase 表的特性 Region包含多行 列族包含多…...

编程日记 2025/5/20 4:24:20

Spring Boot中如何实现异步处理

在 Spring Boot 中实现异步处理可以通过使用 Async 注解和 EnableAsync 注解来实现。以下是如何配置和使用异步处理的步骤和示例代码。 步骤&#xff1a; 启用异步支持&#xff1a; 在 Spring Boot 配置类上使用 EnableAsync 注解启用异步处理。使用 Async 注解异步方法&…...

编程日记 2025/5/24 8:37:39

SSM电子商城系统

&#x1f345;点赞收藏关注 → 添加文档最下方联系方式咨询本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345; 项目视频 电…...

编程日记 2025/5/19 20:09:10

新版IDEA创建数据库表

这是老版本的IDEA创建数据库表&#xff0c;下面可以自己勾选Not null&#xff08;非空),Auto inc&#xff08;自增长),Unique(唯一标识)和Primary key&#xff08;主键) 这是新版的IDEA创建数据库表&#xff0c;Not null和Auto inc可以看得到&#xff0c;但Unique和Primary key…...

编程日记 2025/5/14 17:34:40

二叉树的存储（下）c++

链式存储 我们可以创建两个数组L[N]、r[N]&#xff0c;分别存储i 号结点的左右孩子的编号&#xff0c;这样就可以通过数组下标实现链式访问。 本质上还是孩子表示法&#xff0c;存储的是左右孩子的信息 #include <iostream>using namespace std;const int N 1e6 10; …...

编程日记 2025/5/20 4:09:01

Flutter中PlatformView在鸿蒙中的使用

Flutter中PlatformView在鸿蒙中的使用 概述在Flutter中的处理鸿蒙端创建内嵌的鸿蒙视图创建PlatformView创建PlatformViewFactory创建plugin&#xff0c;注册platformview注册插件 概述 集成平台视图&#xff08;后称为平台视图&#xff09;允许将原生视图嵌入到 Flutter 应用…...

编程日记 2025/5/24 8:39:06

Docker—搭建Harbor和阿里云私有仓库

Harbor概述 Harbor是一个开源的企业级Docker Registry管理项目&#xff0c;由VMware公司开发。‌它的主要用途是帮助用户迅速搭建一个企业级的Docker Registry服务&#xff0c;提供比Docker官方公共镜像仓库更为丰富和安全的功能&#xff0c;特别适合企业环境使用。‌12 Harb…...

编程日记 2025/5/18 6:31:53

一篇博文了解JVM的各个内存区域

​ JVM的内存区域可以细分为程序计数器、虚拟机栈、本地方法栈、堆和方法区 其中&#xff0c;方法区和堆是线程共享的&#xff0c;虚拟机栈、本地方法栈和程序计数器是私有的&#xff1b; 先来说说程序计数器&#xff0c;它也被称为PC寄存器&#xff0c;占据着很小的内存空间…...

编程日记 2025/5/23 12:54:27

无监督学习：聚类、异常检测

聚类 工作原因我对聚类特别熟悉&#xff0c;因此视频课程基本快进看完&#xff0c;不做记录 异常检测 高斯(正态)分布 多特征异常检测 将每个特征作为独立特征&#xff08;实践证明即使不完全独立也影响不大&#xff09;计算高斯分布的参数&#xff0c;然后将待预估样本代入…...

编程日记 2025/5/18 14:01:06

pdf与ofd的区别详细对比

PDF&#xff08;Portable Document Format&#xff09;和OFD&#xff08;Open Fixed-layout Document&#xff09;是两种常见的电子文档格式&#xff0c;它们在设计理念、技术实现、应用场景等方面存在显著差异。以下是对这两种格式的详细对比分析&#xff0c;涵盖其历史背景、…...

编程日记 2025/5/23 0:44:01

DDD架构实战第六讲总结：领域驱动设计中的聚合

云架构师系列课程之DDD架构实战第六讲总结：领域驱动设计中的聚合 聚合提升了对象系统的粒度，保证了业务逻辑的完整性，减少了错误产生的概率 一、引言 本讲将探讨领域驱动设计（DDD）中的重要概念——聚合。聚合是业务完整性的单元，是一个更大力度的封装。在领域驱动设计中…...

编程日记 2025/5/22 16:14:56

CentOS7使用源码安装PHP8教程整理

CentOS7使用源码安装PHP8教程整理 下载安装包解压下载的php tar源码包安装所需的一些依赖扩展库安装前的配置修改配置文件1、进入php8的安装包 配置环境变量开机自启启动服务创建软连接常见问题1、checking for icu-uc > 50.1 icu-io icu-i18n... no2、configure: error: Pa…...

编程日记 2025/5/16 20:50:24

vue3中自定一个组件并且能够用v-model对自定义组件进行数据的双向绑定

1. 基础用法 在 Vue3 中&#xff0c;v-model 在组件上的使用有了更灵活的方式。默认情况下&#xff0c;v-model 使用 modelValue 作为 prop&#xff0c;update:modelValue 作为事件。 1.1 基本示例 <!-- CustomInput.vue --> <template><input:value"mo…...

编程日记 2025/5/21 23:02:06

【win11】解决msrdc.exe窗口启动导致周期性失去焦点

msrdc.exe randomly stealing focus 最近写代码时&#xff0c;经常出现周期性失去焦点的情况非常恼人,不确定是否是Q4的微软更新引起&#xff1f;换了输入法也不行&#xff0c;只能借助工具来查看&#xff1a;大神的工具非常好&#xff1a; 可以发现是remote app 启动了一个UI…...

编程日记 2025/5/6 23:47:07

【2024年终总结】深圳工作生活评测

距离上次写年终总结已经过了一年半了&#xff0c;这一年半中哪怕经历了很多的事情&#xff0c;但是感觉又没发生什么。想写一些骚话&#xff0c;却总觉得自己无法完全表达&#xff0c;便也就这样&#xff0c;静静地记录下这一段时光。 现在是2025年&#xff0c;春节前的时光&am…...

编程日记 2025/5/20 18:49:36

【29】Word：李楠-学术期刊❗

目录 题目​ NO1.2.3.4.5 NO6.7.8 NO9.10.11 NO12.13.14.15 NO16 题目 NO1.2.3.4.5 另存为手动/F12Fn光标来到开头位置处→插入→封面→选择花丝→根据样例图片&#xff0c;对应位置填入对应文字 (手动调整即可&#xff09;复制样式&#xff1a;开始→样式对话框→管理…...

编程日记 2025/5/24 7:01:19

npm常用命令

以往nodejs版本 Node.js — Node.js 版本 CNPM Binaries Mirror 查看当前版本 npm -v 查看node安装在哪里 where node 清除缓存 npm cache clean --force 淘宝镜像&#xff08;只支持下载&#xff0c;不支持上传发布&#xff09; npm config set registry https://reg…...

编程日记 2025/5/20 21:59:11

安装最小化的CentOS7后，执行yum命令报错Could not resolve host mirrorlist.centos.org； 未知的错误

文章目录 安装最小化的CentOS7后&#xff0c;执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知的错误"错误解决方案&#xff1a; 安装最小化的CentOS7后&#xff0c;执行yum命令报错"Could not resolve host: mirrorlist.centos.org; 未知…...

编程日记 2025/5/22 10:07:06

现代 JavaScript 的入门教程

现代 JavaScript 的定义 现代 JavaScript 通常指的是自 ECMAScript 2015&#xff08;也称为 ES6&#xff09;以来的一系列语言更新和改进&#xff0c;以及随之而来的开发工具、库和框架的生态系统。这些变化不仅增强了 JavaScript 的功能性和表达能力&#xff0c;还推动了更高…...

编程日记 2025/5/23 10:36:05

linux naive代理设置

naive linux客户端 Release v132.0.6834.79-2 klzgrad/naiveproxy GitHub Client setup Run ./naive with the following config.json to get a SOCKS5 proxy at local port 1080. {"listen": "socks://127.0.0.1:1080","proxy": "htt…...

编程日记 2025/5/22 8:16:11

Java数据结构 (链表反转（LinkedList----Leetcode206))

1. 链表的当前结构 每个方框代表一个节点&#xff0c;每个节点包含两个部分&#xff1a; 左侧的数字&#xff1a;节点存储的值&#xff0c;例如 45、34 等。右侧的地址&#xff08;如 0x90&#xff09;&#xff1a;表示该节点 next 指针指向的下一个节点的内存地址。 例子中&a…...

编程日记 2025/5/22 21:34:17

游戏与硬件深度协同，打造更精细的体验优化

高画质的游戏往往带来手机的发热和卡顿从而影响游戏体验。开发者希望能够获取到手机运行的实时状态&#xff0c;从而能够进行主动的负载调节&#xff0c;将手机发热时游戏体验影响降到最低&#xff1b;同时手机也可以通过游戏传入的关键场景如"正在下载资源"“团战中…...

编程日记 2025/5/21 8:48:16

C++实现设计模式---命令模式 (Command)

命令模式 (Command) 命令模式 是一种行为型设计模式&#xff0c;它将请求封装为一个对象&#xff0c;从而使得可以用不同的请求对客户端进行参数化、对请求排队或记录日志&#xff0c;以及支持可撤销的操作。 意图 将操作的调用者与接收者分离&#xff0c;通过将请求封装为独…...

编程日记 2025/5/22 14:26:04

office 2019 关闭word窗口后卡死未响应

最近关闭word文件总是出现卡死未响应的状态&#xff0c;必须从任务管理器才能杀掉word 进程&#xff0c;然后重新打开word再保存&#xff0c;很是麻烦。&#xff08;#其他特征&#xff0c;在word中打字会特别变慢&#xff0c;敲击键盘半秒才出现字符。&#xff09; office官网…...

编程日记 2025/5/19 10:18:43

flutter入门系列教程＜三＞：tabbar的高度自适用，支持无限滚动

背景 在之前的文章中&#xff0c;简介了tabbar组件的使用&#xff0c;它通常用于顶部放置tabbar标签页头&#xff0c;内容全部都是TabbarView的全部内容&#xff0c;且内容通常是占满屏幕的&#xff08;尽可能大&#xff09;&#xff0c;如下&#xff1a; 但是有时候我们需要…...

编程日记 2025/5/24 10:06:04

前端三件套详解之 HTML

HTML&#xff1a; 师承b站pink老师【黑马程序员pink老师前端入门教程&#xff0c;零基础必看的h5(html5)css3移动端前端视频教程】 HTML概述 超文本标记语言&#xff08;英语&#xff1a;HyperText Markup Language&#xff0c;简称&#xff1a;HTML&#xff09;是一种用于创…...

编程日记 2025/5/19 13:46:54

【pytorch 】miniconda python3.11 环境安装pytorch

ubuntu24.04 miniconda python3.11 环境安装pytorch 组件：langgraph本身不需要有一些模型是需要的：python3.11环境：报错ModuleNotFoundError: No module named ‘torchaudio’ ModuleNotFoundError: No module named ‘torchaudio’File "/root/miniconda3/envs/05_ep_…...

编程日记 2025/5/23 14:43:24

支持大功率输出高速频闪的图像处理用光源控制器

机器视觉系统中的光源控制器在确保图像质量、提高系统稳定性、降低能耗以及方便系统扩展和升级等方面发挥着重要作用。它可提供稳定光源&#xff0c;调节参数&#xff0c;另外具有操作便捷性。 下面我们来看Gardasoft的光源控制器&#xff0c;Gardasoft拥有作为图像处理用LED光…...

编程日记 2025/5/20 17:01:07

使用 Python 和 Tesseract 实现验证码识别

验证码识别是一个常见且实用的技术需求&#xff0c;尤其是在自动化测试和数据采集场景中。通过开源 OCR&#xff08;Optical Character Recognition&#xff0c;光学字符识别&#xff09;工具 Tesseract&#xff0c;结合 Python 的强大生态&#xff0c;我们可以高效实现验证码识…...

编程日记 2025/5/19 3:47:19