跳到主要内容

1774.最接近目标价格的甜点成本

链接：1774.最接近目标价格的甜点成本
难度：Medium
标签：数组、动态规划、回溯
简介：返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

题解 1 - cpp​

  • 编辑时间：2022-12-04
  • 执行用时：76ms
  • 内存消耗：9.4MB
  • 编程语言：cpp
  • 解法介绍：dfs。
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ans = baseCosts[0], n = toppingCosts.size();
        function<void(int, int)> dfs = [&](int cur, int idx) {
            if (abs(cur - target) < abs(ans - target) || abs(cur - target) == abs(ans - target) && cur < ans) ans = cur;
            if (idx == n) return;
            dfs(cur, idx + 1);
            dfs(cur + toppingCosts[idx], idx + 1);
            dfs(cur + toppingCosts[idx] * 2, idx + 1);
        };
        for (auto &cost : baseCosts) dfs(cost, 0);
        return ans;
    }
};