Medium

题目描述

你想制作甜点并准备购买原料。你有 n 种冰淇淋底料口味和 m 种配料可供选择。制作甜点时必须遵循以下规则：

  • 必须恰好选择一种冰淇淋底料
  • 可以添加一种或多种配料，也可以不添加任何配料
  • 每种配料最多可以添加两次

给你三个输入：

  • baseCosts，长度为 n 的整数数组，其中 baseCosts[i] 表示第 i 种冰淇淋底料的价格
  • toppingCosts，长度为 m 的整数数组，其中 toppingCosts[i] 表示第 i 种配料的价格
  • 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，因为它是较小的成本。

约束条件：

  • n == baseCosts.length
  • m == toppingCosts.length
  • 1 <= n, m <= 10
  • 1 <= baseCosts[i], toppingCosts[i] <= 10^4
  • 1 <= target <= 10^4

解题思路

这是一道动态规划或者回溯枚举的问题。由于数据规模较小（n, m ≤ 10），我们可以用回溯法枚举所有可能的组合。

核心思路：

  1. 枚举底料：遍历每种冰淇淋底料作为基础成本
  2. 回溯配料：对于每种配料，我们有3种选择（添加0次、1次或2次）
  3. 剪枝优化：当当前成本已经超过目标值太多时，可以提前剪枝
  4. 更新答案：维护与目标值最接近的成本，如果距离相同则选择较小的成本

算法步骤：

  • 初始化结果为最大值
  • 遍历每个底料成本
  • 对于每个底料，使用DFS回溯枚举所有配料组合
  • 在回溯过程中，对每种配料选择添加0次、1次或2次
  • 更新与目标值最接近的成本

优化技巧：

  • 当当前成本超过目标值且距离已经大于当前最优解时剪枝
  • 由于每种配料最多添加2次，状态空间是 3^m，完全可以接受

这种方法时间复杂度较高但实现简单，适合小规模数据。也可以考虑使用动态规划，但回溯法在这里更直观。

代码实现

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int result = INT_MAX;
        
        for (int base : baseCosts) {
            backtrack(base, 0, toppingCosts, target, result);
        }
        
        return result;
    }
    
private:
    void backtrack(int currentCost, int index, vector<int>& toppingCosts, int target, int& result) {
        // 更新最接近的成本
        if (abs(currentCost - target) < abs(result - target) || 
            (abs(currentCost - target) == abs(result - target) && currentCost < result)) {
            result = currentCost;
        }
        
        // 剪枝：如果当前成本已经超过目标太多，不继续搜索
        if (index >= toppingCosts.size() || currentCost > target + abs(result - target)) {
            return;
        }
        
        // 对当前配料选择添加0次、1次或2次
        for (int count = 0; count <= 2; count++) {
            backtrack(currentCost + count * toppingCosts[index], index + 1, toppingCosts, target, result);
        }
    }
};

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        self.result = float('inf')
        
        def backtrack(current_cost, index):
            # 更新最接近的成本
            if (abs(current_cost - target) < abs(self.result - target) or 
                (abs(current_cost - target) == abs(self.result - target) and current_cost < self.result)):
                self.result = current_cost
            
            # 剪枝：如果当前成本已经超过目标太多，不继续搜索
            if index >= len(toppingCosts) or current_cost > target + abs(self.result - target):
                return
            
            # 对当前配料选择添加0次、1次或2次
            for count in range(3):
                backtrack(current_cost + count * toppingCosts[index], index + 1)
        
        for base in baseCosts:
            backtrack(base, 0)
        
        return self.result

public class Solution {
    private int result = int.MaxValue;
    
    public int ClosestCost(int[] baseCosts, int[] toppingCosts, int target) {
        foreach (int baseCost in baseCosts) {
            Backtrack(baseCost, 0, toppingCosts, target);
        }
        
        return result;
    }
    
    private void Backtrack(int currentCost, int index, int[] toppingCosts, int target) {
        // 更新最接近的成本
        if (Math.Abs(currentCost - target) < Math.Abs(result - target) || 
            (Math.Abs(currentCost - target) == Math.Abs(result - target) && currentCost < result)) {
            result = currentCost;
        }
        
        // 剪枝：如果当前成本已经超过目标太多，不继续搜索
        if (index >= toppingCosts.Length || currentCost > target + Math.Abs(result - target)) {
            return;
        }
        
        // 对当前配料选择添加0次、1次或2次
        for (int count = 0; count <= 2; count++) {
            Backtrack(currentCost + count * toppingCosts[index], index + 1, toppingCosts, target);
        }
    }
}

var closestCost = function(baseCosts, toppingCosts, target) {
    let closest = baseCosts[0];
    
    function dfs(index, currentCost) {
        if (Math.abs(currentCost - target) < Math.abs(closest - target) || 
            (Math.abs(currentCost - target) === Math.abs(closest - target) && currentCost < closest)) {
            closest = currentCost;
        }
        
        if (index >= toppingCosts.length || currentCost >= target) {
            return;
        }
        
        // Try 0, 1, or 2 of current topping
        dfs(index + 1, currentCost);
        dfs(index + 1, currentCost + toppingCosts[index]);
        dfs(index + 1, currentCost + 2 * toppingCosts[index]);
    }
    
    for (let baseCost of baseCosts) {
        dfs(0, baseCost);
    }
    
    return closest;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × 3^m)n为底料数量，m为配料数量，每种配料有3种选择(0次、1次、2次)
空间复杂度O(m)递归调用栈的深度为配料数量