Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Help needed in problem D from today's LeetCode Weekly contest

Revision en2, by meiniak, 2020-08-16 13:43:05

Here is the problem link and the solution. I have wrote a recusive solution with memoization to not re compute the sub-problems which have been computed. But i am getting Runtime error due to too much memory allocation in unordered map. How can i optimize it to get A.C ?

My solution :

long long recur(long long n){
    if(n==0) return 0;
    else if(memo.find(n)!=memo.end()){
        return memo[n];
    }
    else{
        long long a = n%3 == 0 ? 1 + recur(n-(2*n)/3) : INT_MAX;
        long long b = n%2 == 0 ? 1 + recur(n-(n/2)) : INT_MAX;
        long long c = 1 + recur(n-1);
        vector<long long> v = {a,b,c};
        memo[n] = *min_element(v.begin(),v.end());
        return memo[n];
    }
}
Tags dp with recursion, leetcode

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English meiniak 2020-08-16 13:43:05 203
en1 English meiniak 2020-08-16 13:40:23 1129 Initial revision (published)