LeetCode 题解工作台
最接近目标价格的甜点成本
你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则： 必须选择 一种 冰激凌基料。 可以添加 一种或多种 配料，也可以不添加任何配料。 每种类型的配料 最多两份 。 给你以下三个输入： baseCosts ，一个长度为 n 的整数数组，其…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
每种类型的配料最多可以选两份，因此，我们可以复制一份配料，然后利用 `DFS` 枚举子集之和。在实现上，我们可以只枚举一半的配料的所有子集和，然后在另一半配料子集和中，利用二分查找找到最接近的配料。 时间复杂度 $O(n \times 2^m \times \log {2^m})$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：
- 必须选择 一种 冰激凌基料。
- 可以添加 一种或多种 配料，也可以不添加任何配料。
- 每种类型的配料 最多两份 。
给你以下三个输入：
baseCosts，一个长度为n的整数数组，其中每个baseCosts[i]表示第i种冰激凌基料的价格。toppingCosts，一个长度为m的整数数组，其中每个toppingCosts[i]表示 一份 第i种冰激凌配料的价格。target，一个整数，表示你制作甜点的目标价格。
你希望自己做的甜点总成本尽可能接近目标价格 target 。
返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。
示例 1：
输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10 输出：10 解释：考虑下面的方案组合（所有下标均从 0 开始）： - 选择 1 号基料：成本 7 - 选择 1 份 0 号配料：成本 1 x 3 = 3 - 选择 0 份 1 号配料：成本 0 x 4 = 0 总成本：7 + 3 + 0 = 10 。
示例 2：
输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18 输出：17 解释：考虑下面的方案组合（所有下标均从 0 开始）： - 选择 1 号基料：成本 3 - 选择 1 份 0 号配料：成本 1 x 4 = 4 - 选择 2 份 1 号配料：成本 2 x 5 = 10 - 选择 0 份 2 号配料：成本 0 x 100 = 0 总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。
示例 3：
输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9 输出：8 解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。
示例 4：
输入：baseCosts = [10], toppingCosts = [1], target = 1 输出：10 解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。
提示：
n == baseCosts.lengthm == toppingCosts.length1 <= n, m <= 101 <= baseCosts[i], toppingCosts[i] <= 1041 <= target <= 104
解题思路
方法一：枚举子集和 + 排序 + 二分查找
每种类型的配料最多可以选两份，因此，我们可以复制一份配料，然后利用 DFS 枚举子集之和。在实现上，我们可以只枚举一半的配料的所有子集和，然后在另一半配料子集和中，利用二分查找找到最接近的配料。
时间复杂度 。
相似题目：
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess the candidate’s ability to identify the right problem-solving pattern for state transitions and dynamic programming.
- question_mark
Evaluate whether they can efficiently manage the search space using dynamic programming or brute force.
- question_mark
Look for understanding of backtracking as a technique to optimize the search for solutions.
常见陷阱
外企场景- error
Not properly handling the combination of base costs and toppings, leading to inefficient or incorrect solutions.
- error
Misunderstanding the problem’s constraints, resulting in an overcomplicated approach when brute force would suffice.
- error
Failing to optimize by pruning unnecessary branches during backtracking, leading to excessive computation.
进阶变体
外企场景- arrow_right_alt
Increase the number of base flavors or topping types, testing the scalability of the solution.
- arrow_right_alt
Introduce a minimum cost constraint, where the total dessert cost must exceed a certain threshold.
- arrow_right_alt
Expand the problem to allow for more complex dessert types with multiple layers or categories of toppings.