LeetCode 1402. Reducing Dishes

November 10, 2020

The first example that LeetCode gives shows that we can't do this greedily. We might want to take on some early negative like-time coefficients in order to increase the value of later dishes.

This is kinda like the knapsack problem, but with a dimension based on what is already in the bag (the index offset matters). I'm going to write a recursive solution with this subproblem:

Input: current index offset, remaining dishes to consider.
Step: For each remaining dish, consider and compare the value from including vs not including it next (recursively).
Output: The higher value.

Dishes can be made in any order, and we will always have a higher total satisfaction with higher value dishes made at a higher index. So, we can start by sorting our input list and then considering dishes one by one in order.

We can use tuples and cache subproblem answers. There are $O(n)$ index offsets and $O(n)$ possible lists of remaining dishes, so the total runtime with caching is $O(n^2)$ .

from typing import List, Tuple, Dict
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.maxSatisfaction([-1,-8,0,5,-9]), 14)
        self.assertEqual(self.s.maxSatisfaction([4,3,2]), 20)
        self.assertEqual(self.s.maxSatisfaction([-1,-4,-5]), 0)
        self.assertEqual(self.s.maxSatisfaction([-2,5,-1,0,3,-3]), 35)
        self.assertEqual(self.s.maxSatisfaction([34,-27,-49,-6,65,70,72,-37,-57,92,-72,36,6,-91,18,61,77,-91,5,64,-16,5,20,-60,-94,-15,-23,-10,-61,27,89,38,46,57,33,94,-79,43,-67,-73,-39,72,-52,13,65,-82,26,69,67]), 45811)

    def test_empty(self):
        self.assertEqual(self.s.maxSatisfaction([]), 0)

class Solution:

    def helper(self, offset: int, dish_index: int, dishes: List[int], c: Dict[Tuple[int, int], int]) -> int:
        if dish_index >= len(dishes):
            return 0
        cached = c.get((offset, dish_index))
        if cached != None:
            return cached
        sat_with = dishes[dish_index]*(offset+1) + self.helper(offset+1, dish_index+1, dishes, c)
        sat_without = self.helper(offset, dish_index+1, dishes, c)
        max_sat = max(sat_with, sat_without)
        c[(offset, dish_index)] = max_sat
        return max_sat

    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        return self.helper(0, 0, sorted(satisfaction), {})

if __name__ == "__main__":
    unittest.main()