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]; } }

Auto comment: topic has been updated by meiniak (previous revision, new revision, compare).Editorial of the contest

Thanks for sharing my screencast :)

I have couple of question,

Is bfs sometimes can act as a more faster way than dfs ?

Also,the states in dfs fashion are more intuitive as dp[n] = min(dp[n-1],dp[n/2],dp[n/3) + 1 as i did in the above solution , if i can't reach x'th state from n state i return INT_MAX.

Why my solution is having stack overflow, is it due to c++ recursion limit, or my map is having 1e9 keys which is causing overlimit.

Can you explain me how to define dp states if we use bfs approach

What paradigm of dp it is called when using dfs or bfs .

Thank you for the kind patience. Will appreciate a lot.

In bfs it would be other way around, dp[x] = minimum number of steps to make x from n

Btw, you can fix your dfs dp by changing it to

`dp[n] = min(n % 2 + recur(n / 2), n % 3 + recur(n / 3))`

.Got it, Thanx