Spoj Problem--> Coins Recursive method.

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

COINS - Bytelandian gold coins

A Coin at a Moment can be changed to three coins (n/2) ,(n/3) , (n/4). Here Map is used to save the 

result in a current state ( dp ) , The saved result can be used next time it is used,

#include<bits/stdc++.h>

using namespace std;

map<long long int,long long int > dp;

long long int brk(long long int n)

{

    if(dp[n])

        return dp[n];

    if(n<12)

        return n;

   long long int ct=0;

  if(n>=12)

    {

      ct+=brk(n/2);

      ct+=brk(n/3);

      ct+=brk(n/4);

    }

  return dp[n]=ct;

}

int main()

{

 long long int n;

 while(scanf("%lld",&n)!=EOF)

 {

  cout<<brk(n)<<endl;

  dp.clear();

 }

return 0;

}