Alternate way of declaring a large array on heap

See more:

recursion

C++14

I was trying to solve the question on basic recursion using memoization https://www.spoj.com/problems/COINS/

NOTE-> max value of n is 1 000 000 0000

I definitely must add memoization to solve this problem
But when i am declaring array of size `1 000 000 000` compiler is saying std::bad_alloc
If I don't declare this much size than very large nearly equal to 100000000(greater then array size) then I am getting segmentation fault

well some people recommended me to use map ,in map also we have to insert all the
key and assign the value -1
otherwise when recursion will start like for some very large how we can a map return value which is not stored as a key till now

Can someone help how map is going to work here to optimize space complexity in this case ?

What I have tried:

#include<bits/stdc++.h>
using namespace std;
vector <int> dp(100000,-1);
int exchange(int n){
    if(n<12)
        return n;
    if(dp[n]!=-1)
        return dp[n];
    return dp[n] = exchange(n/2)+exchange(n/3)+exchange(n/4);
}
int main(){
 //   int t;
   // cin>>t;
    while(1){
  //      memset(dp,-1,sizeof(dp));
        int n;
        cin>>n;
        cout<<exchange(n)<<endl;
    }

}