Elegant top-down memoization solution in C++


#1
void maxcoinUtil(const vector<int> &A, int lo, int hi, vector<vector<int>> &memo, int sum) {
    if(lo == hi) {
        memo.at(lo).at(hi) = A.at(lo);
        return;
    }
    
   if(memo.at(lo + 1).at(hi) == -1) maxcoinUtil(A, lo + 1, hi, memo, sum - A.at(lo));
   if(memo.at(lo).at(hi - 1) == -1) maxcoinUtil(A, lo, hi - 1, memo, sum - A.at(hi));
    
   memo.at(lo).at(hi) = sum - min(memo.at(lo + 1).at(hi), memo.at(lo).at(hi - 1));
}


int Solution::maxcoin(vector<int> &A) {
    int n = A.size(), sum = accumulate(A.begin(), A.end(), 0);
    vector<vector<int>> memo(n, vector<int> (n, -1));
    maxcoinUtil(A, 0, n - 1, memo, sum);
    return memo.front().back();
}