【LeetCode:1402. 做菜顺序 | 动态规划 + 贪心】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 动态规划 + 贪心
        • 🥦 求解思路
        • 🥦 实现代码 - 缓存
        • 🥦 运行结果
        • 🥦 实现代码 - 动态规划
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 1402. 做菜顺序

⛲ 题目描述

一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间(包含之前每道菜所花费的时间)乘以这道菜的满意程度,也就是 time[i]*satisfaction[i] 。

返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。

你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。

示例 1:

输入:satisfaction = [-1,-8,0,5,-9]
输出:14
解释:去掉第二道和最后一道菜,最大的 like-time 系数和为 (-11 + 02 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。
示例 2:

输入:satisfaction = [4,3,2]
输出:20
解释:可以按照任意顺序做菜 (21 + 32 + 4*3 = 20)
示例 3:

输入:satisfaction = [-1,-4,-5]
输出:0
解释:大家都不喜欢这些菜,所以不做任何菜就可以获得最大的 like-time 系数。

提示:

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

🌟 求解思路&实现代码&运行结果


⚡ 动态规划 + 贪心

🥦 求解思路
  1. 通过理解题目的意思,我们首先知道,可以以任意顺序做菜,其次,我们举几个例子就会发现,如果想要最后的结果大,可以把满意程度大的放到最后来完成。
  2. 为什么呢?一方面是数组中的元素本身就大,另外一方面,放到最后,时间也会很长。如果我们想要最后的结果很大,与这俩个变量又密切的关系。
  3. 其次,就是我们的动态规划,该题目的原型是0-1背包模型。不会的同学可以看看,此处不做过多的讲解。
  4. 具体求解的过程步骤请看下面代码。
🥦 实现代码 - 缓存
class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int n=satisfaction.length;dp=new int[n+1][n+1];for(int i=0;i<=n;i++){Arrays.fill(dp[i],-1);}return process(0,0,satisfaction);}public int process(int i,int cnt,int[] satisfaction){if(i>=satisfaction.length){return 0;}if(dp[i][cnt]!=-1) return dp[i][cnt];int p1=0,p2=0;for(int j=0;j<=i;j++){p1=process(i+1,cnt+1,satisfaction)+(cnt+1)*satisfaction[j];p2=process(i+1,cnt,satisfaction);}return dp[i][cnt]=Math.max(p1,p2);}
}
🥦 运行结果

在这里插入图片描述

🥦 实现代码 - 动态规划
class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int n=satisfaction.length;dp=new int[n+1][n+1];for(int i=0;i<=n;i++){dp[n][i]=0;}  for(int i=n-1;i>=0;i--){int p1=0,p2=0;for(int cnt=n-1;cnt>=0;cnt--){p1=dp[i+1][cnt+1]+(cnt+1)*satisfaction[i];p2=dp[i+1][cnt];dp[i][cnt]=Math.max(p1,p2);}}return dp[0][0];}
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166794.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++前缀和算法的应用:从仓库到码头运输箱子原理、源码、测试用例

本文涉及的基础知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 双指针 单调双向队列 题目 你有一辆货运卡车&#xff0c;你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。 给你…

函数模板和类模板实例介绍

模板&#xff1a;将类型定义为参数&#xff0c;实现类型参数化&#xff0c;实现代码重用。 一、函数模板 格式&#xff1a; &#xff08;template-声明模板的关键字&#xff0c;class修饰形参类型&#xff09; template <class / typename T> 返回类型 函数名&#xff…

顺应趋势,用大数据精准营销抓住大数据时代的机遇

想先问大家一个问题&#xff1a;“你觉得现在的营销好做吗&#xff1f;”想必大多数人在说到自己如何营销这一点上&#xff0c;都有道不完的“苦水”。“现在找客户难&#xff0c;投了几十万的广告费&#xff0c;真正来的客户却少得可怜&#xff0c;平均获客成本高得吓人”一位…

【Leetcode每日一题 2530】「贪心|模拟|优先队列」执行K次操作后的最大分数

2023.10.18 本题重点&#xff1a; 1.优先队列的使用 2.ceil()函数的使用相同的还有floor()函数的使用 题目介绍&#xff1b; 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。 在一步 操作 中&#xff1a; 选出一个满足 0 < i < nums.l…

按键中断控制LED灯亮灭

EXTI—外部中断/事件控制器 EXTI&#xff08;External interrupt/event controller&#xff09;—外部中断/事件控制器&#xff0c;管理了控制器的 20 个中断/事 件线。每个中断/事件线都对应有一个边沿检测器&#xff0c;可以实现输入信号的上升沿检测和下降沿的 检测。EXTI可…

路由器的路由过程

大家好&#xff0c;我叫徐锦桐&#xff0c;个人博客地址为www.xujintong.com。平时记录一下学习计算机过程中获取的知识&#xff0c;还有日常折腾的经验&#xff0c;欢迎大家来访。 路由器是连接不同的局域网的一个设备&#xff0c;它一开始的目的是互联异构网络的。 前言 这里…

阿伐曲泊帕的合并用药方案【医游记】

&#xff08;图片来源于网络&#xff01;&#xff09; 阿伐曲泊帕是一种口服的促血小板生成素受体激动剂&#xff0c;用于治疗择期行诊断性操作或手术的慢性肝病相关血小板减少症的成年患者。本文将介绍阿伐曲泊帕的药理作用和药物相互作用。 药理作用 阿伐曲泊帕可以与人体…

【vSphere 8 自签名证书】企业 CA 签名证书替换 vSphere Machine SSL 证书Ⅱ—— 创建和添加证书模板

目录 博文摘要3. 使用 Microsoft 证书颁发机构创建 Machine SSL 和 Solution User 证书模板3.1 打开 Certificate Template Console3.2 复制模板3.3 修改 Compatibility 选项卡3.4 修改 General 选项卡3.5 修改 Extensions 选项卡3.6 修改 Subject Name 选项卡3.7 确认新模板 4…

粘包和半包问题及解决办法

粘包问题是指数据在传输时&#xff0c;在一条消息中读取到了另一条消息的部分数据&#xff0c;这种现象就叫做粘包。 半包问题是指数据在传输时&#xff0c;接收端只收到了部分数据&#xff0c;而非完整的数据&#xff0c;就叫做半包。 产生粘包和半包问题原因&#xff1a; …

Ubuntu更新镜像源切换

概述 用ubuntu用apt命令&#xff0c;自动安装或更新包的时候&#xff0c;默认的镜像源服务器非常卡&#xff0c;很不方便。切换到国内的镜像源&#xff0c;下载更新非常快。为防止以后忘记&#xff0c;本文以国内服务器阿里巴巴的为例简单描述。 版本 Ubuntu23.10 找到更新…

SOAR安全事件编排自动化响应-安全运营实战

SOAR是最近几年安全市场上最火热的词汇之一。各个安全产商都先后推出了相应的产品&#xff0c;但大部分都用得不是很理想。SOAR不同与传统的安全设备&#xff0c;买来后实施部署就完事&#xff0c;SOAR是一个安全运营系统&#xff0c;是实现安全运营过程中人、工具、流程的有效…

Map<String, Object> 和 com.fasterxml.jackson.databind.node.ObjectNode区别

Map<String, Object>和com.fasterxml.jackson.databind.node.ObjectNode都可以用来表示一个键值对集合&#xff0c;其中键是字符串&#xff0c;值可以是任何对象。 Map<String, Object>是Java标准库中的一种数据结构&#xff0c;用于存储一组键值对。它是一个接口…

4、Kafka 消费者

5.1 Kafka 消费方式 5.2 Kafka 消费者工作流程 5.2.1 消费者总体工作流程 5.2.2 消费者组原理 Consumer Group&#xff08;CG&#xff09;&#xff1a;消费者组&#xff0c;由多个consumer组成。形成一个消费者组的条件&#xff0c;是所有消费者的groupid相同。 • 消费者组内…

【设计模式】解释器模式

文章目录 1.解释器模式定义2.解释器模式的角色3.解释器模式实战案例3.1.场景说明3.2.结构类图3.3.代码实现 4.解释器模式优缺点5.解释器模式适用场景6.解释器模式总结 主页传送门&#xff1a;&#x1f481; 传送 1.解释器模式定义 解析器模式&#xff08;Interpreter Pattern&a…

网络解析(二)

ICMP 报文有很多的类型,不同的类型有不同的代码。最常用的类型是主动请求为 8,主动请求的应答为 0。 ICMP 相当于网络世界的侦察兵。我讲了两种类型的 ICMP 报文,一种是主动探查的查询报文,一种异常报告的差错报文; ping 使用查询报文,Traceroute 使用差错报文。 IP和…

进程(1)——什么是进程?【linux】

进程&#xff08;1&#xff09;——什么是进程&#xff1f;【linux】 一. 什么是进程&#xff1f;二. 管理进程&#xff1a;2.1 怎么管理&#xff1a;2.2 PCB2.3.1 task_struct2.3.2 组织task_struct&#xff1a; 三.查看进程3.1 ps ajx3.2 ls /proc 四. 父子进程4.1 什么是父子…

数据结构——三路划分(快排优化)

刷Leetcode时遇到的问题&#xff0c;用普通的快排去跑&#xff0c;发现有问题。 普通的Hoare或者其他的快排好像都没有直接解决掉这个问题&#xff0c;当一个数重复出现的时候&#xff0c;用普通的快排效率其实并没有那么高。所以&#xff0c;这也是普通快排的缺点之一。 所以&…

基于SSM的仓库管理系统

基于SSM的仓库管理系统的设计与实现【文末源码】 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringSpringMVCMyBatisVue工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 登录界面 管理员界面 员工管理 货物管理 员工界面 摘要 当考虑构建基于…

Git使用入门

一、Git简介 Git 是一个开源的分布式版本控制系统。 Git版本控制的功能为保存不同版本的代码&#xff0c;保存代码的地方叫做仓库。 每个仓库中有多个分支&#xff0c;每个分支上又有很多节点&#xff0c;每个节点代表一个版本&#xff0c;不同的分支可以进行合并&#xff0…