C++ O(n * m * target) DP (Faster than 100%)
Key idea: \nMinimise the absolute difference.\n\nExplanation:\n- We try all possible baseCosts\n- For each baseCost, we need to pick the optimal values of toppi
**Key idea**: \nMinimise the absolute difference.\n\n**Explanation**:\n- We try all possible baseCosts\n- For each baseCost, we need to pick the optimal values of toppings - try all possibilties (dp with memoization)\n\t- For each topping we have 3 choices: \n\t\t- Pick once, twice or dont pick at all\n\t- At each step we choose the one which minimises the absolute difference(closest to target)\n\n**Notes**:\n- Preferring the lower target is taken care off in 2 places\n\t- Custom sort comparator\n\t- As we iterate through baseCosts and keep looking for the minimum - if we encounter the same minDiff again and if totalCost is less than the prev minimum cost then totalCost will be the lower one.\n\n```\nstruct Comp {\n    bool operator()(const int& num1, const int& num2) {\n        if(abs(num1) < abs(num2)) {\n            return true;\n        }\n        \n        if(abs(num1) == abs(num2)) {\n            return num1 < num2;\n        }\n        \n        return false;\n    }\n};\nclass Solution {\n    int n;\n    vector<vector<int>> cache;\n    int getMinDiffTarget(int indx, vector<int>& toppingCosts, int target) {\n\n        if(indx > n - 1 || target <= 0) {\n            return -target;\n        }\n        \n        if(cache[indx][target] != INT32_MAX) {\n            return cache[indx][target];\n        }\n        \n        int choose = getMinDiffTarget(indx + 1, toppingCosts, target - toppingCosts[indx]);\n        int chooseTwice = getMinDiffTarget(indx + 1, toppingCosts, target - (2 * toppingCosts[indx]));\n        int skip = getMinDiffTarget(indx + 1, toppingCosts, target);\n        \n        vector<int> nums = {choose, chooseTwice, skip};\n        sort(nums.begin(), nums.end(), Comp());\n\n        \n        return cache[indx][target] = nums[0];\n    }\npublic:\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        n = toppingCosts.size();\n        int closest_cost = 0;\n        int minDiff = INT32_MAX;\n        cache.resize(n, vector<int>(target, INT32_MAX));\n        for(int baseCost: baseCosts) {\n            int toppingCostTarget = target - baseCost;\n            int diff = getMinDiffTarget(0, toppingCosts, toppingCostTarget);\n            int totalCost = baseCost + toppingCostTarget + diff;\n            int totalDiff = target - totalCost;\n            if(abs(totalDiff) < minDiff) {\n                minDiff = abs(totalDiff);\n                closest_cost = totalCost;\n            } else if(abs(totalDiff) == minDiff && totalCost < closest_cost) {\n                closest_cost = totalCost;\n            }\n        }\n        return closest_cost;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C']