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 : ~~~~~ class Solution { public: unordered_map<long,long> memo; int minDays(int n) { long long num = n; int cnt = 0;
return (int)recur(n); } 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]; } }
}; ~~~~~