## Problem Link

http://www.spoj.com/problems/COINS/

## Problem Description

In this problem, We can exchange each coin of value n with three coins of value (n/2),(n/3),(n/4).

So, we need to find maximum value we can obtain from a coin of n value.

## Concepts Used

This is a straightforward DP problem.

## Code

```
#include<bits/stdc++.h>
using namespace std;
// long long int as resultant value can be greater than 10^9.
long long int dp[10000005];
long long int coins(long long int n)
{
//Base case
if(n==0)
return 0;
// can't store value greater than 10^7 in an array so use recursion
if(n>=10000000)
return max(n,coins(n/2)+coins(n/3)+coins(n/4));
// if dp[n] has already been calculated, then return that value.
if(dp[n]!=0)
return dp[n];
// calculate the value
dp[n]=max(n,coins(n/2)+coins(n/3)+coins(n/4));
return dp[n];
}
long long int n;
int main()
{
/*function to assign 0 to every location in dp array equivalent to
for(i=0;i<sizeof(dp);i++)
dp[i]=0;
but it always intialise the whole array i.e. whole size of dp.
*/
memset(dp,0,sizeof(dp));
// to read untill end of file
while(scanf("%lld",&n)!=EOF)
printf("%lld\n",coins(n));
return 0;
}
```

## Explanation

- Input the values of
`n`

till end of file. - Call the function
`coins(n)`

for each value of`n`

. - An array
`long long int dp[10000005]`

is declared and the values set to 0. Here the limit of n is 10^9 but we can store only upto 10^7 in an array so we create a dp of 10^7 and for bigger values, we just apply recursive method. `dp[i]`

represents the maximum amount we can obtain from coin value`i`

.- So, we memoize the coin values in dp and if(
`dp[i]!=0`

) means it has already been evaluated, then`return dp[i]`

else evaluate it by considering it as

```
dp[i]= max(i,coins(i/2)+coins(i/3)+coins(i/4));
if(n==0)
return 0; // This is base case
```

This content has been helpful to you?

Thanks for contributing!