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

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

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到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>0$ 。

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

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

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

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

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

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

为什么需要对数组进行排序，才可以使用动态规划？
假设现在有 $i$ 道菜，此时 $i$ 道菜中满意度最大的为第 $j$ 道菜，它的满意度 $\text{satisfaction}[j]$ ，假设它在数组中的排序为 $i^{{}^{\prime }}$ ，则此时 $i^{{}^{\prime }}<i$ ，无法取到 $i$ ，即此时它的喜爱时间一定无法取到 $i\times \text{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)$ ，其中 $n$ 表示数组 $satisfaction$ 的长度。排序需要的时间为 $O(n\log n)$ ，求解动态规划需要的时间为 $O(n^2)$ ，因此总的时间复杂度为 $O(n^2)$ 。
• 空间复杂度：$O(n^2)$ ，其中 $n$ 表示数组 $satisfaction$ 的长度。我们需要所有动态规划的子状态，一共有 $n^2$ 中子状态，需要的空间为 $O(n^2)$ 。

---

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

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

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

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

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

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

复杂度分析：

• 时间复杂度：$\mathcal{O}(n\log n)$ ，其中 $n$ 为 $a$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$ 。忽略排序的栈开销。