exchange-coins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll exchangeCoinsTopDown(ll n, ll *dp){
    //Base case
    if(n == 0){
        dp[n] = 0;
        return dp[n];
    }

    //Memoization
    if(dp[n] != 0){
        return dp[n];
    }

    //Recursive Case
    else{
        ll c1 = n/2;
        ll c2 = n/3;
        ll c3 = n/4;
        // cout<<c1<<" "<<c2<<" "<<c3<<'\n';
        return dp[n] = max(n, exchangeCoinsTopDown(c1, dp) + exchangeCoinsTopDown(c2, dp) + exchangeCoinsTopDown(c3, dp));
    }
}

int main(){

    ll n;
    cin>>n;
    ll *dp = new ll[n];

    for(int i = 0; i <= n; i++){
        dp[i] = 0;
    }
    cout<<exchangeCoinsTopDown(n, dp)<<'\n';
    return 0;
}