LeetCode1402.做菜顺序

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

LeetCode1402.做菜顺序【hard】。

题目描述

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

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

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

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

输入输出示例

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

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

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

提示：

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

题目分析

①想要得到最大like-time系数总和，要满足以下几个原则：

  • 满意度为负数的菜尽量不做；
  • 为了让满意度为正数的菜获得更多 like-time 系数，可能要适当地做一些满意度为负数的菜；
  • 满意度越高的菜越要晚做。

②为了满足以上原则，首先必要对数组进行排序，满意度越大的菜越往后排；
③每一次的决策都依赖于当前状态，都影响着后续状态，是很经典的动态规划问题（此处暂不讲解动态规划概念）；
④进行状态定义：明确变量，第x次对第y道菜做出决策，对于每道菜可以选或不选，此时可以转化为 [0 - 1 背包] 问题；用i代表对第i道菜抉择，j代表进行第j次决策，用dp[i][j]代表在前i道菜中进行了j次选择，即在前i道菜中选择了j道时的最大 like-time 系数总和；
⑤分析状态转移方程：前i道菜中选择了j道菜时，有两种情况。第i道菜在第j次选择时被选择了，第i道菜在第j次选择时没有被选择。

  • 第i道菜在第j次选择时被选择了，意味着在前i-1道菜中选择了j-1道菜，同时加上第i道菜的like-time系数，即j * satisfaction[i-1]（满意度数组下标从0开始）。可得公式dp[i][j] = dp[i-1][j-1] + j * satisfaction[i-1]。
  • 第i道菜在第j次选择时没有被选择，意味着第j次选择发生在前i-1道菜之间，即在前i-1道菜中选择了j道，并且 i-1 >= j ，即 i > j。可得公式dp[i][j] = dp[i-1][j], i > j。

题解

题解一：动态规划

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int MaxSatisfaction(int[] satisfaction)
{
    int n = satisfaction.Length;
    //定义一个动态规划数组，dp[i][j]表示前i道菜中选择j道菜时可以得到的最大like-time总和
    int[][] dp = new int[n + 1][];
    for(int i = 0; i < n + 1; i++) {
        dp[i] = new int[n + 1];
    }
    Array.Sort(satisfaction);
    int res = 0;
    for(int i = 1; i < n + 1; i++) {
        for(int j = 1; j < n + 1; j++) {
            dp[i][j] = dp[i - 1][j - 1] + j * satisfaction[i - 1];
            if(i > j) {
                dp[i][j] = Math.Max(dp[i][j], dp[i - 1][j]);
            }
            res = Math.Max(res, dp[i][j]);
        }
    }
    return res;
}

Tips：为什么定义的是int[][] dp = new int[n + 1][]而不是int[][] dp = new int[n][]，是一个小技巧，计算从索引1开始，避免在计算i-1或j-1时还要考虑索引小于0的情况。

题解二：前缀和

一个很妙的解法，涉及到前缀和的解法。
知题解一分析，满意度越高的菜应该越晚做，同时兼做一些满意度为负的菜来增加时间系数。此处有一个简单的数学原理：i * n等于i + i……，n个i相加。我们在排序后，可以从满意度最高的菜开始考虑，这道菜每晚一轮做，相当于增加了一次这道菜的满意值，而n道菜每晚一轮做，相当于把这些菜的满意度都累加一遍。
此时，我们就可以利用一个值sum，来代表选择做这道菜时的收益，等于在此之后选择做的菜满意度累加值加上当前菜的满意度，如果大于0，说明选择做这道菜对于之后的选择来说收益为正，那么我们就可以选择做这道菜，由此可得解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int MaxSatisfaction(int[] satisfaction) {
    Array.Sort(satisfaction);
    int res = 0;
    int sum = 0;
    for(int i = satisfaction.Length - 1; i >=0; i--) {
        sum += satisfaction[i];
        if(sum > 0) {
            res += sum;
        }
    }
    return res;
}