Coins In A Line 2

5, Coins in A Line 2

[5, 1, 2, 10] 一堆有价值的硬币，A和B轮流按顺序抓取，每次能取1个或者2个，问A先手的话能否获胜。

State: 使用一维数组去记录还剩x个硬币时，当前选手可以获得的最大价值.

Function: dp[i] = sum[i] - min(dp[i-1], dp[i-2])

Initialize: dp[0] = 0

         dp[1] = coins[size-1]

         dp[2] = coins[size-1] + coins[size-2]

Answer: dp[n]

/**
 * @param values: a vector of integers
 * @return: a boolean which equals to true if the first player will win
 */
bool firstWillWin(vector<int> &values) {
    // write your code here
    if(values.size() == 0)
    {
        return false;
    }

    vector<int> dp(values.size()+1, 0);
    vector<bool> flag(values.size()+1, false);
    vector<int> sum(values.size()+1, 0);

    for(int i = 1; i<=values.size(); i++)
    {
        sum[i] = sum[i-1] + values[values.size()-i];
    }

    return memSearch(dp, flag, sum, values, values.size())*2 > sum.back();
}

int memSearch(vector<int>& dp, vector<bool>& flag, vector<int>& sum, vector<int>& values, int i)
{
    if(flag[i] == true)
    {
        return dp[i];
    }

    if(i == 0)
    {
        return 0;
    }
    if(i == 1)
    {
        return sum[1];
    }
    if(i == 2)
    {
        return sum[2];
    }

    else
    {
        dp[i] = sum[i] - min(memSearch(dp, flag, sum, values, i-1), memSearch(dp, flag, sum, values, i-2));
    }

    flag[i] = true;
    return dp[i];
}