LeetCode 877. 石子游戏

1、题目

877. 石子游戏

2、题解

首先，一开始我觉得这道题目并不严谨。因为我大略感觉到先手选择的人就能赢得这个游戏，因为你总是可以在当前的选择中选择对自己有利的拿取方式，而后手只能在剩下的机会中选择。可是如果这道题并不限制于偶数堆这个限制的话，先手优势就不存在了（例：【1,100,1】）你怎么拿都是后手赢。所以，我们应该严谨的判断一下数组长度，如果是偶数，就直接返回TRUE，如果是奇数，就使用DP来做即可。
具体看代码。

3、代码

正常解法：

  class Solution {
        public boolean stoneGame(int[] piles) {
            int length=piles.length;
            //偶数直接TRUE，先手胜利；
            if(length%2==0){
                return true;
            }
            //奇数
            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;
        }
    }

不考虑题目扩展的解法：

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

4、执行结果

正常解法：
带了奇偶判断的写法：

image.png

直接使用dp的结果：

image.png

不考虑题目扩展的解法：

image.png