I do not know why but when recursion tries to add value and then to return it that map after return of function deletes all elements, I do not understand in what a problem.
static int SumNum(string target, string m[], map<string, int> memo = {}){
if (memo.find(target) != memo.end()) {
cout << memo.find(target)->second<<"\n";
return memo.find(target)->second;
}
if (target == "") return 1;
int totalCount = 0;
for(auto i = 0;i < 10; i )
{
if (target.find(m[i]) == 0){
int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
totalCount = numOfWays;
}
}
memo.emplace(target, totalCount);
return totalCount;
}
int main(){
string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
string target = "eeeeeeeeefdc";
auto answer = SumNum(target,ar);
cout << answer;
}
CodePudding user response:
I think that @Max meant this:
static int SumNum(std::string target, std::string m[], map<string, int>& memo = {} /* pass by reference */){
if (memo.find(target) != memo.end()) {
std::cout << memo.find(target)->second<<"\n";
return memo.find(target)->second;
}
if (target == "") return 1;
int totalCount = 0;
for(auto i = 0;i < 10; i )
{
if (target.find(m[i]) == 0){
int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
totalCount = numOfWays;
}
}
memo.emplace(target, totalCount);
return totalCount;
}
int main(){
std::string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
std::string target = "eeeeeeeeefdc";
auto answer = SumNum(target,ar);
std::cout << answer;
}
CodePudding user response:
thanks @Max i did like you say
static int SumNum(string target, string m[], map<string, int> *memo = new map<string, int>()) {
if (memo->find(target) != memo->end()) {
cout << memo->find(target)->second<<"\n";
return memo->find(target)->second;
}
if (target == "") return 1;
int totalCount = 0;
for(auto i = 0;i < 10; i )
{
if (target.find(m[i]) == 0){
int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
totalCount = numOfWays;
}
}
memo->emplace(target, totalCount);
return totalCount;
}
int main(){
string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
string target = "eeeeeeeeeeeeefdc";
auto answer = SumNum(target,ar);
cout << answer;
}