➤ Problem Link : COINS
👉 Hint : Simple 1D DP
✅ C++ Solution :
#include <bits/stdc++.h>
using namespace std;
long long int dp[1000007];
long long int solve(long long int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
if(n<=100000 && dp[n]!=-1)
return dp[n];
long long int res1=solve(n/2)+solve(n/3)+solve(n/4);
long long int res2=n;
long long int res=max(res1,res2);
if(n<=100000)
dp[n]=res;
return res;
}
int main()
{
long long int n;
while(scanf("%lld",&n)!=EOF)
{
memset(dp,-1,sizeof(dp));
long long int res=solve(n);
printf("%lld\n",res);
}
return 0;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.