#1774

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Closest Dessert Cost

Find the closest dessert cost to a target by selecting from a list of base flavors and topping combinations using dynamic programming.

array dynamic programming backtracking

Problem Statement

You are tasked with making a dessert using a variety of ice cream base flavors and topping choices. You are given a list of baseCosts representing the prices of the base flavors and toppingCosts representing the price per topping. You must select one base flavor and zero or more toppings, such that the total cost is as close as possible to a given target.

The goal is to return the total cost of the dessert that is closest to the target. If multiple desserts are equidistant from the target, return the one with the lowest cost. You can use dynamic programming or brute force enumeration due to the problem’s manageable constraints.

Examples

Example 1

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10

Output: 10

Consider the following combination (all 0-indexed):

Choose base 1: cost 7
Take 1 of topping 0: cost 1 x 3 = 3
Take 0 of topping 1: cost 0 x 4 = 0 Total: 7 + 3 + 0 = 10.

Example 2

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18

Output: 17

Consider the following combination (all 0-indexed):

Choose base 1: cost 3
Take 1 of topping 0: cost 1 x 4 = 4
Take 2 of topping 1: cost 2 x 5 = 10
Take 0 of topping 2: cost 0 x 100 = 0 Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9

Output: 8

It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

Constraints

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104

Solution Approach

State Transition Dynamic Programming

Dynamic programming can be used to explore all possible base and topping combinations. By treating the problem as a state transition, we can track all possible costs and select the one that is closest to the target. This approach avoids redundant calculations and helps optimize the solution.

Brute Force Enumeration

Given the manageable constraints, you can also use brute force to enumerate all possible combinations of base flavors and toppings. This method simply checks every combination and computes the total cost to find the closest match to the target.

Backtracking Optimization

Backtracking can be useful for pruning unnecessary branches in the search space. As we iterate over the topping options, we can stop early if the cost exceeds the target, reducing computation time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the approach. Brute force would have a time complexity of O(n * 3^m) where n is the number of base costs and m is the number of toppings. State transition dynamic programming can be more efficient, but it requires tracking all possible costs and is influenced by both the base costs and topping combinations.

What Interviewers Usually Probe

Assess the candidate’s ability to identify the right problem-solving pattern for state transitions and dynamic programming.
Evaluate whether they can efficiently manage the search space using dynamic programming or brute force.
Look for understanding of backtracking as a technique to optimize the search for solutions.

Common Pitfalls or Variants

Common pitfalls

Not properly handling the combination of base costs and toppings, leading to inefficient or incorrect solutions.
Misunderstanding the problem’s constraints, resulting in an overcomplicated approach when brute force would suffice.
Failing to optimize by pruning unnecessary branches during backtracking, leading to excessive computation.

Follow-up variants

Increase the number of base flavors or topping types, testing the scalability of the solution.
Introduce a minimum cost constraint, where the total dessert cost must exceed a certain threshold.
Expand the problem to allow for more complex dessert types with multiple layers or categories of toppings.

FAQ

How do I solve the Closest Dessert Cost problem using dynamic programming?

Dynamic programming allows you to track all possible costs for each combination of base and toppings, and select the one closest to the target.

Can brute force be used to solve the Closest Dessert Cost problem?

Yes, brute force is feasible due to the problem's constraints, allowing you to check all possible combinations of base and toppings.

What are the common pitfalls when solving the Closest Dessert Cost problem?

Some pitfalls include inefficient handling of combinations, overcomplicating the solution, and not optimizing the search space using backtracking.

How does backtracking help in the Closest Dessert Cost problem?

Backtracking helps by pruning unnecessary branches of the search, improving efficiency when exploring topping combinations.

What is the time complexity of solving the Closest Dessert Cost problem?

Time complexity depends on the approach: brute force has O(n * 3^m), while dynamic programming’s complexity varies based on how you track costs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def closestCost(
        self, baseCosts: List[int], toppingCosts: List[int], target: int
    ) -> int:
        def dfs(i, t):
            if i >= len(toppingCosts):
                arr.append(t)
                return
            dfs(i + 1, t)
            dfs(i + 1, t + toppingCosts[i])

        arr = []
        dfs(0, 0)
        arr.sort()
        d = ans = inf

        # 选择一种冰激淋基料
        for x in baseCosts:
            # 枚举子集和
            for y in arr:
                # 二分查找
                i = bisect_left(arr, target - x - y)
                for j in (i, i - 1):
                    if 0 <= j < len(arr):
                        t = abs(x + y + arr[j] - target)
                        if d > t or (d == t and ans > x + y + arr[j]):
                            d = t
                            ans = x + y + arr[j]
        return ans

Continue Practicing

#1799 maximize score after n operations #1723 find minimum time to finish all jobs #1655 distribute repeating integers