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

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

暴力

class Solution {
    List<Integer> list = new ArrayList<>();
    int m;
    int t;
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int n = baseCosts.length;
        m = 2 * toppingCosts.length;
        t = target;
        getTopCosts(toppingCosts, 0, 0);
        int res = 0x3f3f3f3f, min = 0x3f3f3f3f;
        for (Integer integer : list) {
            for (int i = 0; i < n; i++) {
                int cost = integer + baseCosts[i];
                if (Math.abs(target - cost) < min) {
                    min = Math.abs(target - cost);
                    res = cost;
                }
                if (Math.abs(target - cost) == min) {
                    res = Math.min(res, cost);
                }
            }
        }
        return res;
    }

    private void getTopCosts(int[] toppingCosts, int k, int sum) {
        if (k >= m) {
            list.add(sum);
            return;
        }
        getTopCosts(toppingCosts, k + 1, sum + toppingCosts[k % toppingCosts.length]);
        getTopCosts(toppingCosts, k + 1, sum);
    }
}

dp

class Solution {
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int x = Arrays.stream(baseCosts).min().getAsInt();
        if (x >= target) {
            return x;
        }
        boolean[] can = new boolean[target + 1];
        int res = 2 * target - x;
        for (int b : baseCosts) {
            if (b <= target) {
                can[b] = true;
            } else {
                res = Math.min(res, b);
            }
        }
        for (int t : toppingCosts) {
            for (int count = 0; count < 2; ++count) {
                for (int i = target; i > 0; --i) {
                    if (can[i] && i + t > target) {
                        res = Math.min(res, i + t);
                    }
                    if (i - t > 0) {
                        can[i] = can[i] | can[i - t];
                    }
                }
            }
        }
        for (int i = 0; i <= res - target; ++i) {
            if (can[target - i]) {
                return target - i;
            }
        }
        return res;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/closest-dessert-cost/solutions/2004210/zui-jie-jin-mu-biao-jie-ge-de-tian-dian-2ck06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。