Daily LeetCode – day0128 1774. Closest Dessert Cost

// 1774. Closest Dessert Cost
class Solution {
    int ans = Integer.MAX_VALUE;
    int minDistanceToTarget = Integer.MAX_VALUE;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        for (int baseCost : baseCosts) {
            addTopping(baseCost, 0, toppingCosts, target);
        }
        return ans;
    }

    private void addTopping(int cost, int index, int[] toppingCosts, int target) {
        int distanceToTarget = Math.abs(cost - target);
        if (distanceToTarget < minDistanceToTarget) {
            ans = cost;
            minDistanceToTarget = distanceToTarget;
        } else if (distanceToTarget == minDistanceToTarget) {
            if (cost < ans) {
                ans = cost;
            }
        }
        if (cost > target || index >= toppingCosts.length) {
            return;
        }
        addTopping(cost, index + 1, toppingCosts, target);
        addTopping(cost + toppingCosts[index], index + 1, toppingCosts, target);
        addTopping(cost + toppingCosts[index] * 2, index + 1, toppingCosts, target);
    }
}

学习笔记：
这是一道又去的题目，制作冰激凌。
用到了深度优先搜索，每一种配料就三种情况，不加，加一份，加两份。
就看最终价格最逼近的情况就可以了。