Concise c++ DFS solution, 6ms


  • 3
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int cost = 0) {
        if (needs < 0)
            return INT_MAX;
    
        int m = cost + needs * price;
    
        for (auto &offer : special) {
            if (cost + offer.back() >= m) // pruning
                continue;
            needs -= offer;
            m = min(m, shoppingOffers(price, special, needs, cost + offer.back()));
            needs += offer;
        }
    
        return m;
    }
    

    with the following operators defined above the Solution class:

    void operator+=(vector<int> &a, const vector<int> &b) {
        for (int i = 0; i < a.size(); i++)
            a[i] += b[i];
    }
    
    void operator-=(vector<int> &a, const vector<int> &b) {
        for (int i = 0; i < a.size(); i++)
            a[i] -= b[i];
    }
    
    bool operator<(const vector<int> &a, const int &n) {
        for (int i : a)
            if (i < n)
                return true;
        return false;
    }
    
    int operator*(const vector<int> &a, const vector<int> &b) {
        int res = 0;
        for (int i = 0; i < a.size(); i++)
            res += a[i] * b[i];
        return res;
    }
    

Log in to reply
 

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