Альтернативный способ объявления большого массива в куче

---

Я пытался решить вопрос о базовой рекурсии с помощью запоминания https://www.spoj.com/problems/COINS/

Примечание-> максимальное значение n составляет 1 000 000 0000

Я определенно должна добавить мемоизация решить эту проблему
Но когда я объявляю массив размером `1 000 000 000` компилятор говорит std::bad_alloc
Если я не объявляю этот большой размер, чем очень большой, почти равный 100000000(больше размера массива), то я получаю ошибку сегментации

ну некоторые люди рекомендовали мне использовать карту ,в карту также мы должны вставить все свои данные.
ключ и присвоить значение -1
в противном случае когда рекурсия начнется как для некоторых очень больших как мы можем сопоставить возвращаемое значение которое до сих пор не хранится в качестве ключа

Может ли кто-нибудь помочь, как карта будет работать здесь, чтобы оптимизировать сложность пространства в этом случае ?

Что я уже пробовал:

#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;
    }

}

---