C++ 6ms Straightforward Solution


  • 0
    G

    Idea: Basically, my method is a brute-force way using DFS. I accelerate it by only diving in next level if the current cost is not greater than some previous total cost. Other explanations are commented in codes.

    class Solution {
        int res = INT_MAX;
        void dfs(vector<int>& price, vector<vector<int>>& special, vector<int> needs, int cost){
            
            // Phase 1: if needs are satisified, update result
            bool emptyneed = true;
            for (int num: needs) 
                if (num != 0){
                    emptyneed = false;
                    break;
                }
            if (emptyneed) {
                res = min(cost, res); 
                return;
            }
            
            // Phase 2: check if there is available special offer
            for (int i = 0; i < special.size(); i++){
                
                bool applicable = true; 
                for (int j = 0 ; j < special[i].size()-1; j++)
                    if (needs[j] < special[i][j]){
                        applicable = false;
                        break;
                    }
                
                if (applicable) {
                    int newCost = cost + special[i].back();
                    if (newCost > res) continue;            
                    // earlier exit, if current cost is already larger than some previous cost
                    
                    vector<int> newNeeds = needs;
                    for (int j = 0 ; j < special[i].size()-1; j++)
                        newNeeds[j] -= special[i][j];
                    dfs(price, special, newNeeds, newCost);
                }
            }
            
            // Phase 3: buy products one-by-one 
            for (int i = 0; i < price.size(); i++){
                if (needs[i] == 0) continue;
                cost += needs[i]*price[i];
                needs[i] = 0;
            }
            dfs(price, special, needs, cost);
        }
    public:
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            dfs(price, special, needs, 0);
            return res;
        }
    };
    

Log in to reply
 

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