C++ Easy commented solution using DP and recursion || 100% faster :)
Hi,\nIts nothing but simple DP and recursion. 1st we need base so for each base run recursion with target-base[i]\nAnd in recursion we have 3 choices at every s
Hi,\nIts nothing but simple DP and recursion. 1st we need base so for each base run recursion with ```target-base[i]```\nAnd in recursion we have 3 choices at every step either choose ```0 or 1 or 2``` toppings. Make according recursion and choose minimum difference.\n\nNote: if we have same difference with target then need to choose minimum i.e. difference is positive.\n\n**If this helps please do UPVOTE or if you have any query or doubt COMMENT it below.**\n```\nclass Solution {\npublic:\n    \n    int solve(vector<int>& top, int t,int ind){\n        \n        if(ind==top.size()) return t;\n        \n\t\t// choose some maximum\n        int res=1e+4;\n\t\t\n\t\t// dont choose any toppings\n        res=min(res,solve(top,t,ind+1));\n\t\t\n\t\t// choose 1 topping\n        if(t>0) {\n            int temp = solve(top,t-top[ind],ind+1);\n            if(abs(temp)<abs(res) or (abs(temp)==abs(res) and temp>res)) res=temp;\n        }\n\t\t\n\t\t// choose 2 toppings\n        if(t>0) {\n            int temp = solve(top,t-2*top[ind],ind+1);\n            if(abs(temp)<abs(res) or (abs(temp)==abs(res) and temp>res)) res=temp;\n        }\n        return res;\n    }\n    \n    \n    int closestCost(vector<int>& base, vector<int>& top, int t) {\n        int n=base.size();\n        int ans;\n        for(int i=0;i<n;i++){\n            int temp = (solve(top,t-base[i],0));\n            if(abs(temp)<abs(ans) or(abs(temp)==abs(ans) and temp>ans)) ans=temp;\n        }\n        return t-ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C', 'C++']