Solved! Leetcode 1402. Reducing Dishes

Problem Description

source: https://leetcode.com/problems/reducing-dishes/description/

Reducing Dishes

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Example 1:
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-11 + 02 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (21 + 32 + 4*3 = 20)

Example 3:
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

Constraints:

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

Java

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        int[][] memo = new int[satisfaction.length+1][satisfaction.length+1];
        for(int[] m: memo){
            Arrays.fill(m, -1);
        }
        int max = dfs(satisfaction, 0, 1, memo);
        return max<0?0:max;
    }

    public int dfs(int[] nums, int index, int coeff, int[][] memo){
        if(index >= nums.length){
            return 0;
        }
        if(memo[index][coeff]!=-1){
            return memo[index][coeff];
        }
        int max = Integer.MIN_VALUE;
        for(int i = index;i<nums.length;i++){
            max = Math.max(max, nums[i]*coeff + dfs(nums, i+1, coeff+1, memo));
        }
        memo[index][coeff] = max;
        return max;
    }
}

class Solution {

public int maxSatisfaction(int[] satisfaction) {

Arrays.sort(satisfaction);

int[][] memo = new int[satisfaction.length+1][satisfaction.length+1];

for(int[] m: memo){

Arrays.fill(m, -1);

}

int max = dfs(satisfaction, 0, 1, memo);

return max<0?0:max;

}

public int dfs(int[] nums, int index, int coeff, int[][] memo){

if(index >= nums.length){

return 0;

}

if(memo[index][coeff]!=-1){

return memo[index][coeff];

}

int max = Integer.MIN_VALUE;

for(int i = index;i<nums.length;i++){

max = Math.max(max, nums[i]*coeff + dfs(nums, i+1, coeff+1, memo));

}

memo[index][coeff] = max;

return max;

}

Python

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)
        total = 0
        res = 0
        for d in satisfaction:
            total += d
            if total < 0:  # if total < 0 it means that adding the plate (and the rest of the plates) will just make the sum lower hence not worth it
                break
            res += total
            #print(d, total, res)
            
        return res

class Solution:

def maxSatisfaction(self, satisfaction: List[int]) -> int:

satisfaction.sort(reverse=True)

total = 0

res = 0

for d in satisfaction:

total += d

if total < 0: # if total < 0 it means that adding the plate (and the rest of the plates) will just make the sum lower hence not worth it

break

res += total

#print(d, total, res)

return res

4/5 - (1 vote)

Coddicted

Solved! Leetcode 1402. Reducing Dishes

Table of Contents

Problem Description

Reducing Dishes

Java

Python

Leave a Reply Cancel Reply