c++ recursive solution easy to understand


  • 0
    Q
    class Solution {
    public:
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            int res = 0;
            for(int i=0;i<needs.size();i++)
                res += price[i]*needs[i];
            int t = 0;
            t = dfs(price, special, needs, 0);
            res = min(res,t);
            return res;
        }
        
        int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int cur){
            int t = 0;
            for(int i=0;i<needs.size();i++)
                t += price[i]*needs[i];
            
            for(auto it:special){
                if(compare(it,needs)){
                    update(it,needs,1);
                    t = min(t,dfs(price,special,needs,it.back()));
                    update(it,needs,-1);
                }
            }
                             
            return cur + t;
        }
        
        bool compare(vector<int> a, vector<int> b){ 
            for(int i=0;i<b.size();i++)
                if(a[i] > b[i])
                    return false;
            return true;
        }
        
        void update(vector<int> a, vector<int> &b, int dir){
            for(int i=0;i<b.size();i++)
                b[i] -= dir*a[i];
        }
    };
    

Log in to reply
 

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