Coins In A Line 3

Solution

[3, 2, 3]

一个区间的硬币，A和B互相抽取，每次只能抽取一个，可以从左边或者右边抽，问A先手能否胜利？

因为可以从两边抽，原先的一维DP已经无法满足，所以引出了二维空间DP的概念。

和其他DP一样，状态方程是最重要的。

dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1])

min里面的意思是，让后手的B取的尽量少，这样A在这一轮就尽量多！！！

code

class Solution { public: /**

 * @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;
    }

    int n = values.size();

    vector<vector<int>> dp;
    vector<vector<bool>> flag;
    vector<vector<int>> sum;
    for(int i = 0; i<n; i++)
    {
        vector<int> tmp(n, 0);
        tmp[i] = values[i];
        vector<bool> tmp2(n, false);
        dp.push_back(tmp);
        sum.push_back(tmp);
        flag.push_back(tmp2);
    }

    for(int i = n-1; i >= 0; i--)
    {
        for(int j = i+1; j<n; j++)
        {
            sum[i][j] = sum[i][j-1] + sum[j][j];
        }
    }
    /*
    for(int i = n-1; i >= 0; i--)
    {
        for(int j = i+1; j<n; j++)
        {
            dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1]);
        }
    }

    return dp[0][n-1] * 2 > sum[0][n-1];*/

    return memSearch(dp, flag, sum, 0, n-1)*2>sum[0][n-1];

}

int memSearch(vector<vector<int>>& dp, vector<vector<bool>>& flag, vector<vector<int>>& sum, int i, int j)
{

    if(flag[i][j])
    {
        return dp[i][j];
    }

    if(i > j)
    {
        return 0;
    }

    if(i == j)
    {
        return dp[i][i];
    }

    dp[i][j] = sum[i][j] - min(memSearch(dp, flag, sum ,i+1, j), memSearch(dp, flag, sum, i, j-1));

    flag[i][j] = true;

    return dp[i][j];
}

};