LeetCode: Reducing Dishes

Reducing Dishes

Similar Problems:

• CheatSheet: LeetCode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #knapsack

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 (-1*1 + 0*2 + 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, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.

Example 4:

Input: satisfaction = [-2,5,-1,0,3,-3]
Output: 35

Constraints:

• n == satisfaction.length
• 1 <= n <= 500
• -10^3 <= satisfaction[i] <= 10^3

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

## https://code.dennyzhang.com/reducing-dishes
## Basic Ideas: knapsack problem
##
##   For each dish, whether to prepare it or discard it
##
##  dp(i, time): dish i
##       take it:   
##       discard it:
##
## Complexity: Time O(n*n), Space O(n*n)
class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        n = len(satisfaction)
        dp = [[-sys.maxsize for _ in range(n+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(n):
            v = satisfaction[i]
            # don't take
            for j in range(n+1):
                dp[i+1][j] = dp[i][j]
            # take it
            for j in range(1, n+1):
                # when it's valid
                if dp[i][j-1] != -sys.maxsize:
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j-1]+v*j)
        return max(dp[n])