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

本文属于「征服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>=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$ 表示数组 $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) = 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;
    }
};

复杂度分析

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