LeetCode 1402. 做菜顺序【排序,动态规划；贪心,前缀和,递推】1679

编程入门行业动态更新时间:2024-10-27 07:32:08

LeetCode 1402. 做菜顺序【排序,动态规划；贪心,<a href=https://www.elefans.com/category/jswz/34/1768815.html style= 前缀和,递推】1679"/>

LeetCode 1402. 做菜顺序【排序,动态规划；贪心,前缀和,递推】1679

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解法1 排序+动态规划

假设我们只能选一道菜，那么我们应该如何选择呢？显然，选择满意程度最大的那一道菜 s 0 s_0 s0 是最优的，并且需要验证是否满足 s 0 > 0 s_0 > 0 s0>0 。

假设现在有两道菜 s 0 , s 1 s_0, s_1 s0,s1 ，则此时应该是先选 s 0 s_0 s0 还是先选 s 1 s_1 s1 呢？显然，应先选择小的那道菜，再选择大的那道菜。假设 s 0 < s 1 s_0 < s_1 s0<s1 ，此时如果先选择满意小的菜，再选择满意度大的菜则此时的喜爱时间为 s 0 + 2 s 1 s_0 + 2s_1 s0+2s1 ；此时如果先选择满意大的菜，再选择满意小的菜则此时的喜爱时间为 s 1 + 2 s 0 s_1 + 2s_0 s1+2s0 ，由于 s 0 < s 1 s_0 < s_1 s0<s1 ，显然 s 0 + 2 s 1 > s 1 + 2 s 0 s_0 + 2s_1 > s_1 + 2s_0 s0+2s1>s1+2s0 。

当然上述问题还需要具体分析，因为涉及到 s 0 , s 1 s_0, s_1 s0,s1 可能小于 0 0 0 情形，但无论取值 s 0 , s 1 s_0, s_1 s0,s1 如何，我们都应该尽量先选择满意度小的，后选择满意度大的。可以根据排序不等式得到该结论。

根据上述贪心原则，显然满意度越大的菜越应该尽量越往后选，应对 n n n 道菜按照满意度的大小进行排序，满意度越大的菜应该越往后排。

如果第 i i i 次选了第 j j j 道菜，则此时第 j j j 道菜的喜爱时间为 i × satisfaction [ j ] i \times \textit{satisfaction}[j] i×satisfaction[j] 。对于每道菜来说，可以选或者可以不选，此时~~则可以转换为「 0-1 \text{0-1} 0-1 背包」问题~~，等价于求在 n n n 个物品中选择 m m m 个时可以获得的最大喜爱时间，其中 m ∈ [ 0 , n ] m \in [0,n] m∈[0,n] 。

设 dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j] 表示前 i i i 道菜中选择 j j j 道菜时可以得到的最大喜爱时间，且满足 i ≥ j i \ge j i≥j ，则此时对于第 i i i 道菜来说有以下两种选择：

第 i i i 道菜在第 j j j 次被选择，则此时需要在前 i − 1 i-1 i−1 道菜中选择 j − 1 j-1 j−1 道菜，则此时 dp [ i ] [ j ] = max ⁡ ( dp [ i ] [ j ] , dp [ i − 1 ] [ j − 1 ] + j × satisfaction [ i ] ) \textit{dp}[i][j] = \max(\textit{dp}[i][j], \textit{dp}[i-1][j-1] + j \times \textit{satisfaction}[i]) dp[i][j]=max(dp[i][j],dp[i−1][j−1]+j×satisfaction[i])
第 i i i 道菜在第 j j j 次没有被选择，则此时需要在前 i − 1 i-1 i−1 道菜中选择 j j j 道菜，此时需要满足 i − 1 ≥ j i -1 \ge j i−1≥j ，则此时 dp [ i ] [ j ] = max ⁡ ( dp [ i ] [ j ] , dp [ i − 1 ] [ j ] ) \textit{dp}[i][j] = \max(\textit{dp}[i][j], \textit{dp}[i-1][j]) dp[i][j]=max(dp[i][j],dp[i−1][j])
我们按照上述递推公式计算出 n n n 道菜中选择 x x x 道菜的最大喜爱时间， x x x 的取值为 x ∈ [ 0 , n ] x \in [0, n] x∈[0,n] ，则此时可以得到的最大喜爱时间为 max ⁡ ( dp [ n ] [ x ] ) \max (\textit{dp}[n][x]) max(dp[n][x]) 。

为什么需要对数组进行排序，才可以使用动态规划？
假设现在有 i i i 道菜，此时 i i i 道菜中满意度最大的为第 j j j 道菜，它的满意度 satisfaction [ j ] \textit{satisfaction}[j] satisfaction[j] ，假设它在数组中的排序为 i ′ i^{'} i′ ，则此时 i ′ < i i^{'} < i i′<i ，无法取到 i i i ，即此时它的喜爱时间一定无法取到 i × satisfaction [ j ] i \times \textit{satisfaction}[j] i×satisfaction[j] ，则此时一定无法满足最优解。

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {int n = satisfaction.size();sort(satisfaction.begin(), satisfaction.end());vector<vector<int>> dp(n + 1, vector<int>(n + 1));int ans = 0;// dp[i][j]表示前i道菜中选择j道菜时可以得到的最大喜爱时间// dp[i][j]=max(dp[i][j], dp[i-1][j-1]+j*s[i])// dp[i][j]=max(dp[i][j], dp[i-1][j]), if i-1>=jfor (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i][j] = dp[i - 1][j - 1] + satisfaction[i - 1] * j;if (j < i) dp[i][j] = max(dp[i - 1][j], dp[i][j]);ans = max(ans, dp[i][j]);}}return ans;}
};

复杂度分析：

时间复杂度： O ( n 2 ) O(n^2) O(n2) ，其中 n n n 表示数组 s a t i s f a c t i o n satisfaction satisfaction 的长度。排序需要的时间为 O ( n log ⁡ n ) O(n\log n) O(nlogn) ，求解动态规划需要的时间为 O ( n 2 ) O(n^2) O(n2) ，因此总的时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
空间复杂度： O ( n 2 ) O(n^2) O(n2) ，其中 n n n 表示数组 s a t i s f a c t i o n satisfaction satisfaction 的长度。我们需要所有动态规划的子状态，一共有 n 2 n^2 n2 中子状态，需要的空间为 O ( n 2 ) O(n^2) O(n2) 。

解法2 贪心+前缀和+递推

为了方便计算，把 a a a 从大到小排序。来看看做 k = 1 , 2 , 3 k=1,2,3 k=1,2,3 道菜时，对应的总和 f ( k ) f(k) f(k) 是多少。

k = 1 k=1 k=1 时，总和为 f ( 1 ) = a [ 0 ] f(1)=a[0] f(1)=a[0] 。
k = 2 k=2 k=2 时，总和为 f ( 2 ) = 2 ⋅ a [ 0 ] f(2)=2⋅a[0] f(2)=2⋅a[0] 。
k = 3 k=3 k=3 时，总和为 f ( 3 ) = 3 ⋅ a [ 0 ] + 2 ⋅ a [ 1 ] + a [ 2 ] f(3)=3\cdot a[0] + 2\cdot a[1] + a[2] f(3)=3⋅a[0]+2⋅a[1]+a[2] 。

为了快速地算出每个 f ( k ) f(k) f(k) ，我们需要找到 f ( k ) f(k) f(k) 的递推式。观察上面列出的式子，你能找到递推式吗？先把 f ( k ) f(k) f(k) 的式子列出来：
f ( k ) = k ⋅ a [ 0 ] + ( k − 1 ) ⋅ a [ 1 ] + ⋯ + 2 ⋅ a [ k − 2 ] + a [ k − 1 ] f(k)=k\cdot a[0] + (k-1)\cdot a[1] + \cdots + 2\cdot a[k-2] + a[k-1] f(k)=k⋅a[0]+(k−1)⋅a[1]+⋯+2⋅a[k−2]+a[k−1]
每一项去掉一个 a [ i ] a[i] a[i] ，得到：
( k − 1 ) ⋅ a [ 0 ] + ( k − 2 ) ⋅ a [ 1 ] + ⋯ + a [ k − 2 ] (k-1)\cdot a[0] + (k-2)\cdot a[1] + \cdots + a[k-2] (k−1)⋅a[0]+(k−2)⋅a[1]+⋯+a[k−2]
这正是 f ( k − 1 ) f(k-1) f(k−1) 。所以有
f ( k ) = f ( k − 1 ) + ( a [ 0 ] + a [ 1 ] + ⋯ + a [ k − 1 ] ) f(k) = f(k-1) + (a[0] + a[1] + \cdots + a[k-1]) f(k)=f(k−1)+(a[0]+a[1]+⋯+a[k−1])
右边的和式是 a a a 的前缀和，我们可以一边遍历 a a a ，一边把 a [ i ] a[i] a[i] 累加到一个变量 s s s 中。这样就可以 O ( 1 ) \mathcal{O}(1) O(1) 地从 f ( k − 1 ) f(k-1) f(k−1) 递推得到 f ( k ) f(k) f(k) 了。

答案为 f ( 0 ) , f ( 1 ) , f ( 2 ) , ⋯ , f ( n ) f(0), f(1), f(2),\cdots, f(n) f(0),f(1),f(2),⋯,f(n) 中的最大值。

实现细节：想一想 s s s 是怎么变化的。由于数组是从大到小排序的，（一般地）会先遇到正数，再遇到负数，所以（一般地） s s s 会先变大，再变小。
如果 s ≤ 0 s\le 0 s≤0 ，那么后面的 a [ i ] a[i] a[i] 必然都是负数，我们不可能得到更大的 f ( k ) f(k) f(k) ，退出循环。
代码实现时，可以只用一个变量表示 f f f 。由于在退出循环之前 s s s 都是大于 0 0 0 的，所以 f ( k ) > f ( k − 1 ) f(k) > f(k-1) f(k)>f(k−1) ，因此退出循环时的 fff 就是最终答案。

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {sort(satisfaction.rbegin(), satisfaction.rend());int f = 0; // f(0) = 0int s = 0; // satisfaction 的前缀和for (int x : satisfaction) {s += x;if (s <= 0) { // 后面不可能找到更大的 f(k)break;}f += s; // f(k) = f(k-1) + s}return f;}
};

复杂度分析：