Leetcode 博弈論先手必勝解題思路（Leetcode 292/877）

 就一個一個的枚舉，1-3塊手頭，先手必勝，4塊手頭，先手必負，

5個石頭，拿一個，讓對手變成4個，那麼必勝。

8個石頭，不管怎麼拿，必負。

是以可歸納出4的倍數的石頭時，都必輸。

這種是最簡單的博弈論問題，因為容易枚舉，很容易找到規律。

這種存在一個遞歸枚舉的做法，非常經典，但是會逾時。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return helper(0,piles.size()-1,0,0,true,piles);
    }

    bool helper(int left, int right, int scoreA, int scoreB, bool turnA, vector<int>& piles){
        if(left==right){
            return scoreA>scoreB;
        }
        if(turnA){
            if(helper(left+1,right,scoreA+piles[left],scoreB,!turnA,piles)||helper(left,right-1,scoreA+piles[right],scoreB,!turnA,piles)) return true;
        }else{
            if(helper(left+1,right,scoreA,scoreB+piles[left],!turnA,piles)&&helper(left,right-1,scoreA,scoreB+piles[right],!turnA,piles)) return true;
        }
        return false;
    }
};