How do I approach the 'Reducing Dishes' problem in dynamic programming?

Start by sorting the dishes by satisfaction, and then use dynamic programming to track the best possible sum of like-time coefficients while considering subsets of dishes.

What is the time complexity of the 'Reducing Dishes' problem?

The typical time complexity is O(n log n), which comes from sorting the dishes and then calculating the dynamic programming values.

How does the greedy approach help in solving this problem?

The greedy approach ensures that higher satisfaction dishes are cooked earlier, maximizing their contribution to the like-time coefficient.

What should I focus on to optimize space complexity for this problem?

You should store only the necessary intermediate results, rather than recalculating them at each stage, to reduce space usage.

Can I solve the 'Reducing Dishes' problem without sorting the satisfaction array?

No, sorting the dishes by satisfaction is crucial to maximizing the like-time coefficient and achieving an optimal solution.

#1402

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

做菜顺序

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。一道菜的「 like-time 系数」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是 time[i] * satisfaction[i] 。返回…

数组动态规划贪心排序

题目描述

一个厨师收集了他 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

lightbulb

解题思路

方法一：贪心 + 排序

假如我们只选择一道菜，那么我们应该选择满意度最大的那道菜 $s_0$ ，并且判断 $s_0$ 是否大于 0，如果 $s_0 \leq 0$ ，那么我们就不做菜了，否则我们做这道菜，得到的总满意度为 $s_0$ 。

假如我们选择两道菜，那么我们应该选择满足度最大的两道菜 $s_0$ 和 $s_1$ ，满意度为 $s_1 + 2 \times s_0$ ，此时要保证选择之后的满意度大于选择之前的满意度，即 $s_1 + 2 \times s_0 > s_0$ ，即只要满足 $s_1 + s_0 > 0$ ，我们就可以选择这两道菜。

依此类推，我们可以得到一个规律，即我们应该选择满意度最大的 $k$ 道菜，并且保证前 $k$ 道菜的满意度之和大于 $0$ 。

在实现上，我们可以先对所有菜的满意度进行排序，然后从满意度最大的菜开始选择，每次累加当前这道菜的满意度，如果累加的结果小于等于 $0$ ，那么我们就不再选择后面的菜了，否则我们就选择这道菜。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        ans = s = 0
        for x in satisfaction:
            s += x
            if s <= 0:
                break
            ans += s
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the dynamic programming approach. The solution typically runs in O(n log n) due to sorting and the dynamic programming step, where `n` is the number of dishes. The space complexity is O(n), as we need to store intermediate results for each subset of dishes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently use dynamic programming with state transitions to reduce computation time?
question_mark
Does the candidate recognize the importance of sorting dishes in decreasing order of satisfaction for optimizing results?
question_mark
Is the candidate able to optimize the space complexity while maintaining correctness in the dynamic programming approach?

warning

常见陷阱

外企场景

error
Not considering the importance of sorting dishes, which can lead to suboptimal solutions.
error
Confusing the order of operations in dynamic programming, such as forgetting to update previous states or incorrectly tracking the maximum sum.
error
Overcomplicating the space complexity, when it can be reduced by storing only necessary results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the satisfaction values are all negative? Can the algorithm still function effectively?
arrow_right_alt
How would this problem change if there were a maximum limit on how many dishes could be prepared?
arrow_right_alt
How would the solution scale if the number of dishes is significantly larger than 500?

help

常见问题

外企场景

继续练习

#1363 形成三的最大倍数 #1262 可被三整除的最大和 #646 最长数对链