30 ms Java dfs solution


  • 0
    X
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int[] min = new int[]{Integer.MAX_VALUE};
            dfs(needs, special, price, 0, min, 0);
            return min[0];
        }
        public void dfs(List<Integer> needs, List<List<Integer>> special, List<Integer> price, int cur, int[] min, int level) {
            if (level == special.size()) {
                for (int i = 0; i < needs.size(); i++) {
                    cur += needs.get(i) * price.get(i);
                }
                min[0] = Math.min(min[0], cur);
                return;
            }
            boolean notEnough = true;
            List<Integer> sp = special.get(level);
            for (int i = 0; notEnough; i++) {
                for (int j = 0; j < needs.size(); j++) {
                    if (needs.get(j) - i * sp.get(j) < 0) {
                        notEnough = false;
                        break;
                    }
                }
                if (notEnough) {
                    for (int j = 0; j < needs.size(); j++) {
                        needs.set(j, needs.get(j) - i * sp.get(j));
                    }
                    dfs(needs, special, price, cur + i * sp.get(sp.size() - 1), min, level + 1);
                    for (int j = 0; j < needs.size(); j++) {
                        needs.set(j, needs.get(j) + i * sp.get(j));
                    }                
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.