1、題目

877. 石子游戲

2、題解

首先，一開(kāi)始我覺(jué)得這道題目并不嚴(yán)謹(jǐn)。因?yàn)槲掖舐愿杏X(jué)到先手選擇的人就能贏得這個(gè)游戲，因?yàn)槟憧偸强梢栽诋?dāng)前的選擇中選擇對(duì)自己有利的拿取方式，而后手只能在剩下的機(jī)會(huì)中選擇?？墒侨绻@道題并不限制于偶數(shù)堆這個(gè)限制的話，先手優(yōu)勢(shì)就不存在了（例：【1,100,1】）你怎么拿都是后手贏。所以，我們應(yīng)該嚴(yán)謹(jǐn)?shù)呐袛嘁幌聰?shù)組長(zhǎng)度，如果是偶數(shù)，就直接返回TRUE，如果是奇數(shù)，就使用DP來(lái)做即可。
具體看代碼。

3、代碼

正常解法：

  class Solution {
        public boolean stoneGame(int[] piles) {
            int length=piles.length;
            //偶數(shù)直接TRUE，先手勝利；
            if(length%2==0){
                return true;
            }
            //奇數(shù)
            int[][] dp = new int[length][length];
            for (int i = 0; i < length; i++) {
                dp[i][i]=piles[i];
            }
            for(int i=length-1;i>=0;i--){
                for (int j = i+1; j <length; j++) {
                    dp[i][j]=Math.max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);
                }
            }
            return dp[0][length-1]>0;
        }
    }

不考慮題目擴(kuò)展的解法：

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

4、執(zhí)行結(jié)果

正常解法：
帶了奇偶判斷的寫法：

image.png

直接使用dp的結(jié)果：

image.png

不考慮題目擴(kuò)展的解法：

image.png