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

leetcode 2944.购买水果需要的最小金币

思路:dp

这道题一开始想的时候并不会,但是看到了有些水果可以买也可以不买,所以就想到了选择与不选择的思路。

对于每一个水果,我们都有买和不买的选择,但是我们的第一个水果是一定要买的。然后再往后推导。

用dp[][2]来表示这个状态方程。dp[i][1]表示的就是选择买第i个水果,另外一个状态就是不买了。

但是大家也发现了,不买水果的话,我们还需要知道的一点就是前面是否有买过水果能让当前这个水果不用买呢?这是这道题的核心问题。既然不买,那么肯定就必须是前面买过的水果里有覆盖这个水果的。

这怎么办呢?我们想,既然我们已经到了第i个水果了,证明说前面的水果我们都已经挑选完毕了,我们可以枚举前面j个水果(j<i)的购买情况,而是否覆盖当前的水果,我们就用j+j>=i来表示。为什么呢?第一个j代表我们已经买到当前的水果j了,然后这个水果又可以往后覆盖j个水果让他免费。并且这个>=i是包含我们当前水果的判断。

dp[i][0]=min(dp[i][0],dp[j][1])这就是不选择买当前水果的方程。

好了,我解决最棘手的问题之后,剩下的就好解决了,选择买这个水果那么方程就是:

dp[i][1]=min(dp[i-1][0],dp[i-1][1])+prices[i-1](这里i是从2开始的)

上代码:

class Solution {
public:int minimumCoins(vector<int>& prices) {int n=prices.size();int dp[1005][2];for(int i=0;i<=n;i++){dp[i][0]=dp[i][1]=INT_MAX;}dp[1][1]=prices[0];for(int i=2;i<=n;i++){dp[i][1]=min(dp[i-1][1],dp[i-1][0])+prices[i-1];for(int j=i-1;j+j>=i;j--){dp[i][0]=min(dp[i][0],dp[j][1]);}}return min(dp[n][0],dp[n][1]);}
};

相关文章:

leetcode 2944.购买水果需要的最小金币

思路&#xff1a;dp 这道题一开始想的时候并不会&#xff0c;但是看到了有些水果可以买也可以不买&#xff0c;所以就想到了选择与不选择的思路。 对于每一个水果&#xff0c;我们都有买和不买的选择&#xff0c;但是我们的第一个水果是一定要买的。然后再往后推导。 用dp[]…...

算法人生(14):从“探索平衡策略”看“生活工作的平衡之道”

在强化学习中&#xff0c;有一种策略叫“探索平衡策略Exploration-Exploitation Trade-off&#xff09;”&#xff0c;这种策略的核心是在探索未知领域&#xff08;以获取更多信息&#xff09;和利用已知信息&#xff08;来最大化即时回报&#xff09;之间寻求平衡&#xff0c;…...

如何使用Tushare+ Backtrader进行股票量化策略回测

数量技术宅团队在CSDN学院推出了量化投资系列课程 欢迎有兴趣系统学习量化投资的同学&#xff0c;点击下方链接报名&#xff1a; 量化投资速成营&#xff08;入门课程&#xff09; Python股票量化投资 Python期货量化投资 Python数字货币量化投资 C语言CTP期货交易系统开…...

Guid转换为字符串

在理想情况下&#xff0c;任何计算机和计算机集群都不会生成两个相同的GUID。GUID 的总数达到了2128&#xff08;3.41038&#xff09;个&#xff0c;所以随机生成两个相同GUID的可能性非常小&#xff0c;但并不为0。GUID一词有时也专指微软对UUID标准的实现。 (1). GUID&#…...

OpenAI的搜索引擎要来了!

最近的报道和业界泄露信息显示&#xff0c;OpenAI正秘密研发一款新的搜索引擎&#xff0c;可能叫SearchGPT或Sonic&#xff0c;目标是挑战Google的搜索霸权。预计这款搜索引擎可能在5月9日即将到来的活动中正式亮相。 SearchGPT的蛛丝马迹 尽管OpenAI对SearchGPT尚未表态&…...

PaddlePaddle与OpenMMLab

产品全景_飞桨产品-飞桨PaddlePaddle OpenMMLab算法应用平台...

HBuilderX uniapp+vue3+vite axios封装

uniapp 封装axios 注&#xff1a;axios必须低于0.26.0&#xff0c;重中之重 重点&#xff1a;封装axios的适配器adapter 1.安装axios npm install axios0.26.0创建api文件夹 2.新建adapter.js文件 import settle from "axios/lib/core/settle" import buildURL…...

【网络安全产品】---应用防火墙(WAF)

what Web应用防火墙&#xff08;Web Application Firewall) WAF可对网站或者App的业务流量进行恶意特征识别及防护&#xff0c;在对流量清洗和过滤后&#xff0c;将正常、安全的流量返回给服务器&#xff0c;避免网站服务器被恶意入侵导致性能异常等问题&#xff0c;从而保障…...

C++学习第十二天(继承)

1、继承的概念以及定义 继承的概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行拓展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承呈现了面向对象程序设计的层次结构&#x…...

WPF DataGrid绑定后端 在AutoGeneratingColumn事件中改变列名

public void OnAutoGeneratingColumn(DataGridAutoGeneratingColumnEventArgs e){var propertyDescriptor (PropertyDescriptor)e.PropertyDescriptor;if (propertyDescriptor.IsBrowsable){e.Column.Header propertyDescriptor.DisplayName;}else{e.Cancel true;}}实体类中…...

2024 CorelDraw最新图形设计软件 激活安装教程来了

2024年3月&#xff0c;备受瞩目的矢量制图及设计软件——CorelDRAW Graphics Suite 2024 正式面向全球发布。这一重大更新不仅是 CorelDRAW 在 36 年创意服务历史中的又一重要里程碑&#xff0c;同时也展现了其在设计软件领域不断创新和卓越性能的领导地位。 链接: https://pan…...

双网口扩展IO支持8DO输出

M320E以太网远程I/O数据采集模块是一款工业级、隔离设计、高可靠性、高稳定性和高精度数据采集模块&#xff0c;嵌入式32位高性能微处理器MCU&#xff0c;集成2路工业10/100M自适应以太网模块里面。提供多种I/O&#xff0c;支持标准Modbus TCP&#xff0c;可集成到SCADA、OPC服…...

【负载均衡在线OJ项目日记】编译与日志功能开发

目录 日志功能开发 常见的日志等级 日志功能代码 编译功能开发 创建子进程和程序替换 重定向 编译功能代码 日志功能开发 日志在软件开发和运维中起着至关重要的作用&#xff0c;目前我们不谈运维只谈软件开发&#xff1b;日志最大的作用就是用于故障排查和调试&#x…...

yaml配置文件的在深度学习中的简单应用

1 .创作灵感 小伙伴们再阅读深度学习模型的代码的时候&#xff0c;经常会遇到yaml格式的配置文件。用这个配置文件是因为我们在训练模型的时候会涉及很多的参数&#xff0c;如果这些参数东一个&#xff0c;西一个&#xff0c;我们调起来的时候就会很不方便&#xff0c;所以用y…...

spring boot 核心配置文件是什么?

Spring Boot 的核心配置文件主要是 application.properties 或 application.yml&#xff08;也称为 YAML 格式&#xff09;。这两个文件通常位于项目的 src/main/resources 目录下&#xff0c;用于配置 Spring Boot 应用程序的各种属性和设置。 application.properties&#xf…...

Python的奇妙之旅——回顾其历史

我们这个神奇的宇宙里&#xff0c;有一个名叫Python的小家伙&#xff0c;它不仅聪明&#xff0c;而且充满活力。它一路走来&#xff0c;从一个小小的编程语言成长为如今全球最受欢迎的编程语言之一。今天&#xff0c;我们就来回顾一下Python的历史&#xff0c;看看它如何从一个…...

Flink面试整理-Flink的性能优化策略

Apache Flink 的性能优化是一个多方面的任务,涉及硬件资源、算法选择、配置调整等多个层面。以下是一些常见的 Flink 性能优化策略: 1. 资源分配和管理 合理配置 TaskManager 和 JobManager:根据作业的需求和可用资源,合理分配内存和 CPU 给 TaskManager 和 JobManager。适…...

SpringBoot与SpringMVC的区别

SpringBoot与SpringMVC的区别是什么&#xff1f; SpringBoot和SpringMVC是Java开发中常用的两个框架&#xff0c;它们都是由Spring框架所提供的&#xff0c;但在功能和使用方式上有着一些区别。本文将分别介绍SpringBoot和SpringMVC的特点和区别。 一、SpringBoot的特点&#…...

漏洞挖掘之某厂商OAuth2.0认证缺陷

0x00 前言 文章中的项目地址统一修改为: a.test.com 保护厂商也保护自己 0x01 OAuth2.0 经常出现的地方 1&#xff1a;网站登录处 2&#xff1a;社交帐号绑定处 0x02 某厂商绑定微博请求包 0x02.1 请求包1&#xff1a; Request: GET https://www.a.test.com/users/auth/weibo?…...

电脑屏幕监控软件都有哪些 | 五大好用屏幕监控软件盘点

电脑屏幕监控软件在企业管理、家庭教育等方面发挥着越来越重要的作用。 这些软件通过实时监控电脑屏幕活动&#xff0c;为用户提供了强大的管理和监控功能。 本文将为您盘点五大好用的电脑屏幕监控软件&#xff0c;帮助您更好地了解并选择适合自己的软件。 电脑屏幕监控软件都…...

SystemVerilog内存操作实战:手把手教你实现AXI VIP中的backdoor读写

SystemVerilog内存操作实战&#xff1a;AXI VIP中的backdoor读写技术解析 在硬件验证领域&#xff0c;AXI总线协议因其高性能和灵活性已成为行业标准。验证工程师经常需要与AXI VIP&#xff08;Verification IP&#xff09;交互&#xff0c;其中内存操作是最基础也最关键的环节…...

3个核心方法实现暗影精灵硬件控制与性能调优:告别原厂软件烦恼

3个核心方法实现暗影精灵硬件控制与性能调优&#xff1a;告别原厂软件烦恼 【免费下载链接】OmenSuperHub 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 一、痛点解析&#xff1a;原厂游戏控制软件的三大致命伤 1.1 隐私安全隐患&#xff1a;网络连接背…...

用腾讯云轻量锐驰和对象存储,手把手教你30分钟搞定私人不限速网盘(附SSL证书配置)

零基础30分钟搭建高性能私人网盘&#xff1a;腾讯云轻量锐驰对象存储实战指南 你是否也受够了公有网盘动辄几百KB的下载速度&#xff1f;每次分享文件给朋友&#xff0c;对方总要忍受龟速下载的煎熬。更别提那些突然消失的文件和频繁弹出的会员广告——是时候拥有一个完全自主掌…...

UE5场景过曝/白屏排查指南:从后期处理体积到项目设置的实战修复

1. 当UE5场景变成"雪盲症"时该怎么办&#xff1f; 第一次打开UE5项目看到白茫茫一片的时候&#xff0c;我差点以为显卡烧了。这种场景过曝现象就像在雪山没戴墨镜&#xff0c;所有细节都被强光吞噬。新手遇到这种情况别慌&#xff0c;我整理了从"急救措施"…...

多模态数字人智能交互平台源码获取方式,支持语音克隆+实时渲染,可商用

温馨提示&#xff1a;文末有资源获取方式最近“龙虾AI”的热度很高&#xff0c;似乎人人都想养一个属于自己的数字员工。但现实是&#xff0c;这类技术对普通用户并不友好&#xff1a;部署需要代码、配置需要专人、调试更是门槛重重。更别提高昂的Token消耗&#xff0c;轻度使用…...

分布式电池管理系统:基于微控制器架构的智能电池保护与均衡解决方案

分布式电池管理系统&#xff1a;基于微控制器架构的智能电池保护与均衡解决方案 【免费下载链接】SmartBMS Open source Smart Battery Management System 项目地址: https://gitcode.com/gh_mirrors/smar/SmartBMS SmartBMS是一个开源的智能电池管理系统&#xff0c;专…...

Qwen2.5-VL-7B-Instruct实操手册:对话历史自动保存+一键清空功能详解

Qwen2.5-VL-7B-Instruct实操手册&#xff1a;对话历史自动保存一键清空功能详解 1. 开篇&#xff1a;你的全能视觉助手来了 今天给大家介绍一个特别实用的工具——基于Qwen2.5-VL-7B-Instruct多模态大模型的视觉交互工具。这个工具专门为RTX 4090显卡优化过&#xff0c;用上了…...

离散数学实战:用Python解决图论问题(附完整代码示例)

离散数学实战&#xff1a;用Python解决图论问题&#xff08;附完整代码示例&#xff09; 当你在社交软件上查看"可能认识的人"推荐&#xff0c;或是用导航软件规划最短路线时&#xff0c;背后都在运行图论算法。作为离散数学中最具工程价值的领域&#xff0c;图论将现…...

CTF是什么?一文带你读懂网络安全大赛

CTF是什么&#xff1f;一文带你读懂网络安全大赛 前言 随着大数据、人工智能的发展&#xff0c;人们步入了新的时代&#xff0c;逐渐走上科技的巅峰。 科技是一把双刃剑&#xff0c;网络安全不容忽视&#xff0c;人们的隐私在大数据面前暴露无遗&#xff0c;账户被盗、资金损失…...

提示工程架构师实战手册:2025年基于最新趋势的AI项目设计指南

提示工程架构师实战手册&#xff1a;2025年基于最新趋势的AI项目设计指南 1. 引入与连接&#xff1a;从“写Prompt”到“设计提示系统”的认知跃迁 1.1 一个真实的AI项目痛点 2024年底&#xff0c;某头部电商公司的智能客服项目陷入瓶颈&#xff1a; 用户发“这件衣服洗了会缩水…...