Блог пользователя red_coder

Автор red_coder, 12 лет назад, По-английски

Guys i tried hashing in a problem in which i used top down approach with recursion and made sure that if a subproblem is solved once i dont have to solve it again with STL container "map" but i failed in that.... i declared a map like "map<int,int> A" and when trying to solve a problem with a particular value of "n" i first checked whether it is already solved as the following code....

map<int,int> A;
int solve(int n)
{
    map<int,int>::iterator got= A.find(n);
    if(got!=A.end())
    {
        return got->second;
    }
    else
    {
     //solve the problem and then compute the result. Suppose the result for 'n' is RESULT then
     A[n]= RESULT;
     return A[n];
    }
}

the above code is working fine for small values of "n" but for large values of "n" like n>=100000 its giving runtime error. how to solve this problem.

Also i would like to mention that earlier for memoization i used simple array but that lead to a lot of wastage of space and also it did not work in cases when "n" took large values like upto 10^9. Guys can u help....

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can get run time error Instead of ML.
Provide a link to a problem you trying to solve.