Exchanging coins

#1

I am getting WA

#2

take a look at constraints
0 <= n <= 1 000 000 000
very large
you can’t make such a large dp array
solution is use TopDownDp
store only those value in dp which are smaller than max and for rest use recursion
like this:

ll MAX=1000000;
ll *dp=new ll [MAX];
ll exchangingCoins(ll n){
	// Base case:
		if(n<=1)return n;

	//Recursive Case:
	if(n<MAX){
		if(dp[n]!=0)return dp[n];
		dp[n]=max(n,exchangingCoins(n/2)+exchangingCoins(n/3)+exchangingCoins(n/4));
		return dp[n];
	}
	return max(n,exchangingCoins(n/2)+exchangingCoins(n/3)+exchangingCoins(n/4));

}

i hope this helps
if you have doubts feel free to ask

#3

How can we decide whether top-down will work or bottom-up?

#4

it totally depends on question

if constraints are very large like in this question use top down dp

If time limit/memory is low then use bottom up dp because in top down recursive stack take more memory and time

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.