Java simple DFS solution with detailed explanation (beats 43%)


  • 0
    M

    General idea:
    Since one special offer can be used infinite times. So we can build our recursion tree in the following way:

    There are totally n layers, where n is the type number of special offer.
    At each layer, we calculate the max branches by using current offer according the remaining needs and the item numbers in the offer. At each layer, we also need to calculate the price without using other special offers except current offer.

    In the process, we calculate the price without using any special offer. Use this value as the min value and use it to prune the recursion tree.

    Time = O(n^k), where n is the type number of special offer; k is the max branches in each layer;
    Space = O(n), n layer call stack.

    class Solution {
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            // sanity check; assume everything is normal;
            int[] min = new int[] {Integer.MAX_VALUE};
            dfs(0, 0, price, special, needs, min);
            return min[0];
        }
        
        // index: which special offer we are using;
        // curPrice: prices we paid until now;
        private void dfs(int index, int curPrice, List<Integer> price, List<List<Integer>> special, List<Integer> needs, int[] min) {
            if (index == special.size()) {
                if (noNeeds(needs)) {
                    min[0] = Math.min(min[0], curPrice);
                }
                return;
            }
            // 1. calculate the max branches by using current offer under current needs;
            List<Integer> curOffer = special.get(index);
            int maxBranches = Integer.MAX_VALUE;
            for (int i = 0; i < needs.size(); i++) {
                if (curOffer.get(i) == 0) {
                    continue;
                }
                maxBranches = Math.min(maxBranches, needs.get(i) / curOffer.get(i));
            }
            // 2. scan each maxBranches and recursion;
            for (int i = 0; i <= maxBranches; i++) {
                // prune the branches which are larger than current min;
                if (curPrice + curOffer.get(curOffer.size() - 1) * i > min[0]) {
                    continue;
                }
                // 2a. using current offer i times;
                curPrice += curOffer.get(curOffer.size() - 1) * i;
                decreaseNeeds(needs, curOffer, i);
                // 2b. continue to use other offers;
                dfs(index + 1, curPrice, price, special, needs, min);
                // 2c. calculate the min price without using any other special offers;
                int priceWithoutOffer = calPriceWithoutOffer(needs, price, curPrice);
                // 2d. update global min
                min[0] = Math.min(min[0], priceWithoutOffer);
                // 2e. backtrack to previous states;
                curPrice -= curOffer.get(curOffer.size() - 1) * i;
                increaseNeeds(needs, curOffer, i);
            }
        }
        
        private void decreaseNeeds(List<Integer> needs, List<Integer> curOffer, int times) {
            for (int i = 0; i < needs.size(); i++) {
                int remain = needs.get(i) - curOffer.get(i) * times;
                needs.set(i, remain);
            }
        }
        
        private void increaseNeeds(List<Integer> needs, List<Integer> curOffer, int times) {
            for (int i = 0; i < needs.size(); i++) {
                int remain = needs.get(i) + curOffer.get(i) * times;
                needs.set(i, remain);
            }
        }
        
        private int calPriceWithoutOffer(List<Integer> needs, List<Integer> price, int curPrice) {
            for (int i = 0; i < needs.size(); i++) {
                curPrice += needs.get(i) * price.get(i);
            }
            return curPrice;
        }
        
        private boolean noNeeds(List<Integer> needs) {
            for (int n : needs) {
                if (n != 0) {
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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