免备案自助建站网站,做国际网站有用,开网站 主机 服务器,wordpress全站采集#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜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 求解思路实现代码运行结果 ⚡ 动态规划 贪心 求解思路
通过理解题目的意思我们首先知道可以以任意顺序做菜其次我们举几个例子就会发现如果想要最后的结果大可以把满意程度大的放到最后来完成。为什么呢一方面是数组中的元素本身就大另外一方面放到最后时间也会很长。如果我们想要最后的结果很大与这俩个变量又密切的关系。其次就是我们的动态规划该题目的原型是0-1背包模型。不会的同学可以看看此处不做过多的讲解。具体求解的过程步骤请看下面代码。 实现代码 - 缓存
class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int nsatisfaction.length;dpnew int[n1][n1];for(int i0;in;i){Arrays.fill(dp[i],-1);}return process(0,0,satisfaction);}public int process(int i,int cnt,int[] satisfaction){if(isatisfaction.length){return 0;}if(dp[i][cnt]!-1) return dp[i][cnt];int p10,p20;for(int j0;ji;j){p1process(i1,cnt1,satisfaction)(cnt1)*satisfaction[j];p2process(i1,cnt,satisfaction);}return dp[i][cnt]Math.max(p1,p2);}
} 运行结果 实现代码 - 动态规划
class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int nsatisfaction.length;dpnew int[n1][n1];for(int i0;in;i){dp[n][i]0;} for(int in-1;i0;i--){int p10,p20;for(int cntn-1;cnt0;cnt--){p1dp[i1][cnt1](cnt1)*satisfaction[i];p2dp[i1][cnt];dp[i][cnt]Math.max(p1,p2);}}return dp[0][0];}
} 运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
