Simple recursive solution


  • 0
    A

    Either take the ith offer multiple times, or do not take it at all. If I take the offer, I use the function recursively by updating the needs called "new needs". Quite simple, right ?. Exponential time complexity and linear space complexity because of recursive stack.

    class Solution {
    public:
        int recurse(int i,vector<int>& price, vector<vector<int>>& special, vector<int> needs) {
            if(i==special.size()){
                int base=0;
                for(int k=0;k<needs.size();k++){
                    base += (price[k]*needs[k]);
                }
                return base;
            }
            int a = recurse(i+1,price,special,needs);
            int flag=1;
            int cost=0;
            vector<int> new_needs;
            int min = INT_MAX;
            for(int k=0;k<needs.size();k++){
                if(special[i][k]!=0 && needs[k]/special[i][k]<min)
                    min=needs[k]/special[i][k];
                if(special[i][k]<=needs[k]){
                    //cost += (needs[k]-special[i][k])*price[k];
                    new_needs.push_back(needs[k]-special[i][k]);
                }
                else
                    flag=0;
            }
            if(flag==1){
                if(min==1)
                    cost += special[i][special[i].size()-1]+recurse(i+1,price,special,new_needs);
                else{
                    new_needs.clear();
                    for(int k=0;k<needs.size();k++){
                        new_needs.push_back(needs[k]-(min*special[i][k]));
                    }
                    cost += (min*special[i][special[i].size()-1])+recurse(i+1,price,special,new_needs);
                }
                return a>cost?cost:a;
            }
            else
                return a;
        }
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            return recurse(0,price,special,needs);
        }
    };
    

Log in to reply
 

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