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

• ``````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;
}
};
``````

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