Java | pure recursion | O(N * 3^M)| Any suggestion for further optimization?
Basically, let\'s just traverse all the cases, since m,n <= 10, Time is O(N * 3^M) which is not a huge work, the brute force method is accepted.\nI have tried t
Basically, let\'s just traverse all the cases, since m,n <= 10, Time is O(N * 3^M) which is not a huge work, the brute force method is accepted.\nI have tried to optimize in two ways, it will not improve the big O though.\n* We keep the low and high bound, since the cost is non-decreasing, we can earlier terminate when the cost has already exceeded the high bound. it will reduce time in half in average.\n* We can earlier terminate when we find the target, (the base case doesn\'t favor my optimization, so the code posted below doesn\'t apply such optimization)\n* Please let me know if you get more optimization idea:)\n```\nclass Solution {\n    int low = 0, high = Integer.MAX_VALUE;\n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        for(int i = 0; i < baseCosts.length; i++) {\n            dfs(baseCosts[i], 0, toppingCosts, target);\n        }\n        return low == 0 || high - target < target - low ? high: low;\n    }\n\n    void dfs(int cost, int idx, int[] toppings, int target) {\n        if(cost > high) return;\n        if(cost <= target) low = Math.max(low, cost);\n        else high = Math.min(high, cost);\n        if(idx >= toppings.length) return;\n        for(int i = 0; i <= 2; i++) {\n            dfs(cost + i * toppings[idx], idx+1, toppings, target);\n        }\n    }\n}\n```
['Java']