Play - 1,2,3 cards Alternate

// Given a deck: you can pick 1,2 or 3 first cards and alternate with your opponent
// How do you maximize your points.
// [1,1,1,1,1]   // You choose 3 first cards.
// [100,1,1,1,1] // You choose only one card. So your opponent can't choose 100.
#include <iostream>     // std::cout
#include <vector>
#include <map>

using namespace std;

typedef pair<int,int> pairResult;

pairResult fRecMemo(const vector<int> &v, int idx, map<int, pairResult>& results) {
    if(idx<0)
        return pairResult(0,0);
    if(results.count(idx))
        return results[idx];
    pairResult bestResult;
    int curHand = 0;
    for(int numCards = 1; numCards <=3; numCards++) {
        int curIdx = idx - (numCards-1);
        if(curIdx < 0)
            break;
        curHand += v[curIdx];
        pairResult oponentResult = fRecMemo(v, curIdx-1, results);
        pairResult curResult = pairResult(curHand + oponentResult.second, oponentResult.first); // swapping
        bestResult = numCards == 1 ? curResult : max(bestResult, curResult);
    }
    results[idx] = bestResult;
    return results[idx];
}
pairResult fRecMemo(const vector<int> &v) {
    map<int, pairResult> results;
    return fRecMemo(v, v.size()-1, results);
}

pairResult fBottomUPDP(const vector<int> &v) {
    if (v.size()==0)
        return make_pair(0,0);

    vector<pair<int,int> > results;
    for(int i=0; i<v.size(); i++) {
        int curHand = 0;
        pair<int,int> bestResult;
        for(int numCards = 1; numCards<=min(3,i+1); numCards++) {
            curHand += v[i+1-numCards];
            pair<int,int> oponenteResult(0,0);
            if(i-numCards>=0)
                oponenteResult = results[i-numCards];
            pair<int,int> curResult(curHand + oponenteResult.second, oponenteResult.first);
            if(numCards==1 || curResult.first>bestResult.first)
                bestResult = curResult;
        }
        results.push_back(bestResult);
    }
    return results.back();
}

pairResult fBottomUPDPTempVars(const vector<int> &v) {
    pair<int,int> prevRes[3];
    prevRes[0] = pair<int,int>(0,0);
    for(int i=0; i<v.size(); i++) {
        int curHand = 0;
        pair<int,int> maxR;
        for(int nC=1; nC<=3 && nC<=i+1; nC++) {
            curHand += v[i+1-nC];
            pair<int,int> prevR = prevRes[nC-1];
            pair<int,int> curR(curHand+prevR.second,prevR.first);
            if(nC==1 || curR.first>maxR.first)
                maxR = curR;
        }
        prevRes[2] = prevRes[1];
        prevRes[1] = prevRes[0];
        prevRes[0] = maxR;
    }
    return prevRes[0];
}


int main() {
    vector<int> d; // deck
    d.push_back(-20);
    d.push_back(10);
    d.push_back(1);
    d.push_back(3);
    d.push_back(2);
    d.push_back(1);

    pairResult p4 = fRecMemo(d);
    cout << "Resultado: " << p4.first << " " << p4.second << endl;

    cout << endl << "Compare Memoized x Non-Memoized" << endl;

    vector<int> d2;
    for(int i=0; i<3; i++) {
        for(int j=1; j<=2; j++)
            d2.push_back(j);
        // slow after 34 elements more than 1B calls
        cout << d2.size() << endl;
        pairResult p3 = fBottomUPDP(d2);
        cout << p3.first << " " << p3.second << "\t";
        cout << "Bottom UP DP " << endl;
        p3 = fBottomUPDPTempVars(d2);
        cout << p3.first << " " << p3.second << "\t";
        cout << "Bottom UP DP Temp Vars " << endl;
        p3 = fRecMemo(d2);
        cout << p3.first << " " << p3.second << "\t";
        cout << "Memoized " << endl;
    }

    return 0;
}