638. Shopping Offers

Link

Solution

也是backtrace DFS，判斷取了之後的子問題

  public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return dfs(price, special, needs, 0);
    }
    
    public int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int index){
        int min = buyWithOrigPrice(price, needs);
        for(int i = index; i < special.size(); i++){
            List<Integer> offer = special.get(i);
            List<Integer> temp = new LinkedList<>();
            //check if can take the offer
            for(int j = 0; j < needs.size(); j++){
                if(needs.get(j) - offer.get(j) < 0){
                    temp = null;
                    break;
                }
                temp.add(needs.get(j) - offer.get(j));
            }
            //if can take the offer
            if(temp != null){
                //take, needs 變成 temp
                //check if take the offer can cause the min cost
                min = Math.min(min, offer.get(offer.size()-1) + dfs(price, special, temp, index));
            }
            //不取，因為needs 不變，就繼續
            //skip the offer, i+1
        }
        return min;
    }
    
    public int buyWithOrigPrice(List<Integer> price, List<Integer> needs){
        int cost = 0;
        for(int i = 0; i < needs.size(); i++){
            cost += price.get(i) * needs.get(i);
        }
        return cost;
    }

但不像典型的backtrace 會在迴圈中判斷取或不取某個element。而是巧妙地融入在城市中

而是直接比較take special offer之後，所造成的cost是否比目前的最小值少。

TODO: 如何決定dfs是否回傳值?