题目描述

Alex和Lee用一堆石头玩游戏，有一行偶数堆石头，每堆石头数为piles[i] (piles[i]为正整数)。游戏的目标是拿到越多的石头越好，由于石头总数是奇数，所以没有平局。

Alex和Lee轮流拿石头，Alex首先出发。每回合，玩家从行的开始或结束处获取整堆石头。这种情况一直持续到没有更多的石堆为止，此时石头最多的人获胜。

假设Alex和Lee都采取最优策略，当且仅当亚历克斯赢得比赛时，返回true，否则返回false。

样例

输入: [5,3,4,5]
输出: true
说明: Alex开始拿，并且只能拿开头的5或者结尾的5。假设他拿的是开头的5，那么石头堆还剩下[3,4,5]。
如果Lee拿了3，那么还剩下[4,5]，Alex拿走5，于是Alex石头数是10，Lee石头数是7，Alex赢。
如果Lee拿了5，那么还剩下[3,4]，Alex拿走4，于是Alex石头数是9，Lee石头数是8，Alex赢。
因此对于Alex来说，拿开头的5是必胜策略，于是返回true。

算法1

(动态规划) $O(n^2)$

最直接的想法就是通过深搜，枚举Alex和Lee的拿石头的可能情况，从而判断是否Alex有必胜策略，但是由于在深搜时会枚举到大量重复的情况导致重复搜索浪费时间，因此考虑用动态规划来避免重复。

考虑维护数组dp来记录局部状态的最优情况，dp[i][j] (j>i并且j-i+1为偶数) 表示石堆序列为$[piles[i], piles[i+1], …, piles[j]]$时，Alex最优的情况下与Lee的石头数的差值，例如在样例中，dp[0][2]表示石堆序列为[5,3]的情况下，Alex最多能比Lee多多少个石头，此时Alex先取，拿走5，Lee只能拿3，于是dp[0][2]=5-3=2。

首先，当石堆只有两堆的时候，Alex自然取走最大的那一堆，即dp初始化状态$dp[i][j]=abs(piles[i]-piles[j]) (j=i+1)$

我们认为Alex取走一个石头，Lee再取走一个石头这样一个过程为一轮，于是在石堆为[piles[i], …, piles[j]]的时候，这轮Alex和Lee只可能有四种取法，即：

Alex拿走piles[i], Lee拿走piles[j], 石堆变为$[piles[i+1], …, piles[j-1]]$的情况，
Alex拿走piles[i], Lee拿走piles[i+1], 石堆变为$[piles[i+2], …, piles[j]]$的情况，
Alex拿走piles[j], Lee拿走piles[i], 石堆变为$[piles[i+1], …, piles[j-1]]$的情况，
Alex拿走piles[j], Lee拿走piles[j-1], 石堆变为$[piles[i], …, piles[j-2]]$的情况。

因此动归数组的状态转移公式为
dp[i][j] = max{piles[i]-piles[j]+dp[i+1][j-1], piles[j]-piles[i]+dp[i+1][j-1],
piles[i]-piles[i+1]+dp[i+2][j], piles[j]-piles[j-1]+dp[i][j-2]}

最后只需要判断dp[0][piles.length()-1]是否大于0即可。

时间复杂度分析：需要计算二维dp数组，复杂度为$O(n^2)$。

C++ 代码

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int dp[505][505];
        memset(dp,0,sizeof(dp));
        for(int len = 2;len<=piles.size();len+=2){
            for(int i = 0;i<piles.size()&&i+len-1<piles.size();i++){
                int j = i+len-1;
                if(len==2){//初始情况
                    dp[i][j] = abs(piles[i]-piles[j]);
                }
                else{
                    dp[i][j] = 0;//状态转移
                    if(abs(piles[i]-piles[j])+dp[i+1][j-1]>dp[i][j])
                        dp[i][j]=abs(piles[i]-piles[j])+dp[i+1][j-1];
                    if(piles[i]-piles[i+1]+dp[i+2][j]>dp[i][j])
                        dp[i][j] = piles[i]-piles[i+1]+dp[i+2][j];
                    if(dp[i][j-2]+piles[j]-piles[j-1]>dp[i][j])
                        dp[i][j] = dp[i][j-2]+piles[j]-piles[j-1];
                }
            }
        }
        return dp[0][piles.size()-1]>0;
    }
};

算法2

(寻找必胜策略) $O(1)$

由于石堆数一定是偶数，考虑将石堆分为两部分，即偶数下标的堆和奇数下标的堆，记为$P_{even}$和$P_{odd}$，有：

$P_{even}=[piles[0], piles[2], …, piles[n-2]]$
$P_{odd}=[piles[1], piles[3], …, piles[n-1]]$

由于Alex先取，那么Alex有策略可以保证自己取的石堆为$P_{even}$或者是$P_{odd}$，例如他如果想取的序列为$P_{even}$，那么首先他先取piles[0]，然后Lee就只能取piles[1]或者piles[n-1]，如果Lee取了piles[1]，那么Alex取piles[2]，如果Lee取了piles[n-1]，那么Alex取piles[n-2]，依次类推，于是最后Alex能保证自己取到的序列为$P_{even}$，Lee取到的序列为$P_{odd}$。相反，如果Alex想取序列$P_{odd}$，那么他只需要先取piles[n-1]，然后每次都取剩下的序列里面的奇数下标的堆即可。

因此，Alex具有选择权，可以选择自己的序列是$P_{even}$还是$P_{odd}$，他只需要比较这两个序列的石堆的数目和，选择数目和较大的序列来取就行了，因此只要石堆数是偶数，Alex一定赢。

时间复杂度分析：直接返回true，O(1)

C++ 代码

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};