import java.util.*;
public class ExchangingCoins {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dp = new int[n+1];
for(int i=0;i<=n;i++) {
dp[i] = i;
}
for(int i=0;i<=n;i++) {
dp[i] = Math.max(dp[i],dp[i/2]+dp[i/3]+dp[i/4]);
}
System.out.println(dp[n]);
}
}
//when I checked with given example I got the correct answer but in test cases im getting run error
since 0 <= n <= 1 000 000 000 as given. When you create an array of size n +1 and n = 10^9, the program runs out of memory. Instead of a dp solution use a recursive solution.
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.