LC-1402. 做菜顺序（记忆化搜索 ==＞ 动态规划、贪心）

1402. 做菜顺序

困难

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

记忆化搜索 ==> 动态规划

class Solution {int[] satisfaction;int[][] cache;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);this.satisfaction = satisfaction;int n = satisfaction.length;cache = new int[n][n];for(int i = 0; i < n; i++)Arrays.fill(cache[i], -1);return dfs(0, 0);}// 定义dfs(i, cnt) 表示 枚举到i，0-i中选择了cnt个菜，可以获得的最大系数总和// 转移 每个菜肴可以选或者不选public int dfs(int i, int cnt){if(i == satisfaction.length){return 0;}if(cache[i][cnt] >= 0) return cache[i][cnt];int res = 0;res = Math.max(res, dfs(i+1, cnt+1) + (cnt+1) * satisfaction[i]);res = Math.max(res, dfs(i+1, cnt));return cache[i][cnt] = res;}
}

转动态规划

class Solution {public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int n = satisfaction.length;int[][] f = new int[n+1][n+1];int res = 0;for(int i = 0; i < n; i++){for(int j = 0; j <= i; j++){// 选f[i+1][j+1] = f[i][j] + satisfaction[i] * (j+1);if(j+1 < i)// 不选f[i+1][j+1] = Math.max(f[i+1][j+1], f[i][j+1]);res = Math.max(res, f[i+1][j+1]);}}return res;}
}

贪心

https://leetcode.cn/problems/reducing-dishes/solutions/2492854/mei-ju-zuo-ji-dao-cai-tan-xin-pythonjava-k7w2/?envType=daily-question&envId=2023-10-22

class Solution {/**贪心1. a[i]大的菜要后做   1*4+2*3 < 1*3+/*42. 将nums从大到小排序令k表示做的菜f(k) = k*a[0] + (k-1)*a[1] + ... + 2*a[k-2] + a[k-1]每一项去掉一个a[i]，得到 f(k-1)(k-1)*a[0] + (k-2)*a[1] + ... + a[k-2]即 f(k) = f(k-1) + (a[0] + a[1] + .. + a[k-1])右边的和式是 a 的前缀和，可以一遍遍历a，一边将a[i]累加到一个变量s中*/public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int f = 0; // f(0) = 0int s = 0;for(int i = satisfaction.length-1; i >= 0; i--){s += satisfaction[i];if(s <= 0){ // 后面不可能找到更大的f(k)break;}f += s; // f(k) = f(k-1) + s}return f;}
}