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

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

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

为什么需要对数组进行排序，才可以使用动态规划？
假设现在有 $i$ 道菜，此时 $i$ 道菜中满意度最大的为第 $j$ 道菜，它的满意度 $\textit{satisfaction}[j]$ ，假设它在数组中的排序为 $i^{'}$ ，则此时 $i^{'} < i$ ，无法取到 $i$ ，即此时它的喜爱时间一定无法取到 $\times \textit{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>=j
        for (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$ 表示数组 $s a t i s f a c t i o n$ 的长度。排序需要的时间为 $O(n\log n)$ ，求解动态规划需要的时间为 $O(n^2)$ ，因此总的时间复杂度为 $O(n^2)$ 。
空间复杂度： $O(n^2)$ ，其中 $n$ 表示数组 $s a t i s f a c t i o n$ 的长度。我们需要所有动态规划的子状态，一共有 $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)$ 。所以有
$\cdots + a[k-1])$
右边的和式是 $a$ 的前缀和，我们可以一边遍历 $a$ ，一边把 $a [i]$ 累加到一个变量 $s$ 中。这样就可以 $\mathcal{O}(1)$ 地从 $f (k - 1)$ 递推得到 $f (k)$ 了。

答案为 $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) = 0
        int 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;
    }
};