C++, DFS, memorization( vector<int> could not be as key of unordered_map)


  • 0
    J
    class Solution {
    public:
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            unordered_map<string,int> memorization;
            /*** in C++, we can not define the vector<int> as key
            unordered_map<vector<int>,int>memorization;*/
            return dfs(price,special,needs,memorization);
        }
    int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs,unordered_map<string,int> memorization)
    {
        string _needs = convert(needs);
        if(memorization.find(_needs)!=memorization.end()) 
            return memorization[_needs];
        int ans = dotproduct(price,needs);
        for(int i = 0;i<special.size();i++)
        {
            int j = 0;
            vector<int>clone = needs;
            for(;j<needs.size();j++)
            {
                if(special[i][j]>needs[j]) 
                    break;
                else
                    clone[j] = needs[j]-special[i][j];
            }
            if(j == needs.size())
                ans = min(ans,special[i][j]+dfs(price,special,clone,memorization));
        }
        memorization[_needs] = ans;
        return ans;
    }
        
    private:
        string convert(vector<int>needs)
        {
            string result;
            for(int i = 0;i<needs.size();i++) result = result+to_string(needs[i])+",";
            return result.substr(0,result.size()-1);    
        }
        int dotproduct(vector<int>prices,vector<int>needs)
        {
            int sum = 0;
            for(int i = 0;i<prices.size();i++) sum+=prices[i]*needs[i];
            return sum;
        }
    };
    

Log in to reply
 

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