Problem

1774. Closest Dessert Cost

Since the data size is not large, we can enumerate all possible combinations of bases and toppings.

Dynamic programming

1. For bases, we can only choose one base.
2. For toppings, we can choose any types of toppings, and up to two toppings of each type. That means for each type of topping, we can choose not to use it, use it once, or use it twice. With this information we can calculate all possible costs of toppings.
3. All the possible combinations of bases and toppings can be calculated by ways to choose bases * ways to choose toppings.
4. With all the possible combinations of costs, we compare them with our target and keep track the minimum difference between each combination and the target, and the combination that produces such minimum difference. We choose the minimum such combination cost as our our final answer.

Possible base costs

All the elements in baseCosts array.

Possible topping costs

1. The minimium topping costs is 0, the case that we do not use any toppings.

2. The maximum topping costs is 2 * (sum of all topping costs).

3. For any number between the minimum and maximum costs, we can calculate whether that number is possible by using what’s already possible (dynamic programming, using the solution of problem of smaller size to solve problem of larger size). Let’s define an array DP, where DP[i] stands for whether cost of i is possible,

   • Base case. By choosing no toppings at all or choosing all the toppings twice.

   DP[0] = true
   DP[sum] = true  # sum = 2 * (sum of toppingCosts)

   • Transition Function.

   DP[i + toppingCost] = true if DP[i] == true
   DP[i + 2 * toppingCost] = true if DP[i] == true

Pseudo Code

bool[] calculatePossibleToppingCosts(int[] toppingCosts)
   sum = 2 * sum of toppingCosts
   Define a boolean array DP of size sum
   DP[0] = true                         # base case

   for toppingCost in toppingCosts
      for i = sum to 0                  # loop backward
         if (!DP[i])
            continue

         if i + toppingCosts <= sum
            DP[i + toppingCost] = true

         if i + 2 * toppingCost <= sum
            DP[i + 2 * toppingCost] = true

   return DP

Why do we loop the DP array backward?

The answer is to avoid double counting. Let’s see an example of what happens if we loop DP forward. Let toppingCosts = [2, 3]

Expected DP

Actual DP

By looping DP forward, we have an extra true value for DP[9], because DP[3] is double counted. Double counting not only happens when toppingCost = 3, it also happens when toppingCost = 2.

When toppingCost = 2, we increase i from 0 to sum

As i increases from 1 to 2, we calcuate DP array with DP[0] = DP[2], DP[4] = true. For DP[4] = true, it means we’ve already chosen the topping of cost = 2 twice. If we continue with DP[4 + 2] and DP[4 + 2 * 2], we are choosing more than 2 parts of the topping (cost = 2). The same case applies to toppingCost = 3.

Conclusion

By looping the DP array backward, the value of higher index will not be reused. Therefore the double counting is avoided.

DFS

// use recursion to enumerate all possible combination costs