Exchanging Coins problem

#1

i am not getting question
anyone please explain me
for test cases
input
12
output
13

case 2
input
17
output
?

#2

for input 17 answer is 17…

#3

it means for prime number answer remain as it is.
and answer of any number n can’t exceed n+1. always less than or equal to n+1.
am i right ?

#4

bro its a normal dp Q. Whats role of prime number in this ?

#5 
#include<bits/stdc++.h>
using namespace std;

long long int dp[1000000];

long long int coins(long long int n){
     if(n<=1000000 && dp[n] != -1)
          return dp[n];
     //base  case
     if(n <= 11){
          dp[n] = n;
          return dp[n];
     }
     long long ans = max(n,coins(n/2)+coins(n/3)+coins(n/4));
     if(n <= 1000000)
          dp[n] = ans;//memoize the answer
     return ans;
}
int main(){
     ios::sync_with_stdio(0);

  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
     long long int n,i;
     
     for(i=0;i<=1000000;i++){
          dp[i] = -1;
     }
     
     cin>>n;
     cout<<coins(n);
     
     return 0;
}
#6

i am not getting your code. how you thinking.
please explain.

#7

its just a normal dp where i am calling all the possible states and storing the state once computed if you are not getting this logic then i would suggest you to practice basic dp Q’s. And only practice can help you to approach dynamic programming Q’s.

#8

i am understanding memoization but the condition
n<=1000000
n<=11
i am not getting.

if(n<=1000000 && dp[n] != -1)
return dp[n];
//base case
if(n <= 11){
dp[n] = n;
return dp[n];
}

#9

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.

1 Like
#10

can you please explain about my above comment.