LeetCode每日一题06-16

题目：877. 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5] 输出：true 解释：亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

解题思路：

由于每次只能取第一个或者最后一个，因此剩下的石头堆都是连续的，也就可以看成一个区间。由于俩人都发挥出最佳水平，那么问题就简化为每次取首部或者尾部的石头堆中石头数量最多的直到石头堆为空，这种情况可以使用递归解决，但对于该问题测试用例来说递归的时间复杂度太高了，并且其中存在大部分重复的操作，故可以使用动态规划进行简化。

对于动态分析解法，首先需要创建一个二维数组dp[i] [j]，其i与j的大小等于石头堆数组的长度，接着可以分为三个步骤分析：

第一步：确定元素的意义

在dp数组中[i，j]代表从下标i到下标j区间内的两个玩家石头数量差值的最大值（记为最大分差） 因此i>j的位置是无意义的

第二步：确定元素之间的关系

由题意可知，玩家每次只可以在[i，j]区间中选择i或者j的元素，

①当玩家1选择了i的元素，那么玩家2可以选择的就是i+1或者j，对于玩家2来说就是[i+1，j]的最大分差，也就是dp[i+1] [j]，因此[i，j]的最大分差就是piles[i]- dp[i+1] [j]

②当玩家1选择了j的元素，那么玩家2可以选择的就是i或者j-1，对于玩家2来说就是[i,j-1]的最大分差，也就是dp[i] [j-1]， 因此[i,j]的最大分差就是piles[j]- dp[i] [j-1] 综上，[i,j]的值即是 ①与②的最大值 max( piles[i]- dp[i+1] [j]，piles[j]- dp[i] [j-1] )

第三步：找出初始条件

由第一步可知，i与j代表的是区间的左右值，那么当左值等于右值时就意味着区间只有一个元素了， 因此初始条件即是i==j，此时只剩下一堆石头，玩家没得选只能拿它，因此dp[i] [i]就等价于piles[i]

假设传入的数组piles为｛6, 4, 3, 5｝

那么可建立一个用于存储区间最大分差的二维数组dp[4] [4]

首先是初始条件，当i==j时，代表只剩下一堆石头，此时dp[i] [i]的值就是piles[i]的值

接着是剩下两堆石头的情况

接着是剩下三堆石头的情况

最后是四堆石头的情况，也就是游戏开始的状态

由此可以发现，只要刚开始时玩家1与玩家2的最大分差大于0，即dp[0] [j]>0，就可以表示玩家1赢玩家2 (Alex win Lee)，因此此题只需要返回dp[0] [j]>0的结果即可

代码：

public boolean stoneGame(int[] piles) {
    int len = piles.length;
    int[][] dp = new int[len][len];
    for (int i = 0; i < len; i++) {
        dp[i][i] = piles[i];
    }
    for (int i = len - 2; i >=0; i--) {
        for (int j = i+1; j <len; j++) {
            dp[i][j] = Math.max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);
        }
    }
    return dp[0][len-1]>0;
}

效率分析：

时间复杂度为O(n^2)

空间复杂度为O(n^2)

数学解法（一行代码）

由题意可以看出来，这个游戏没有平局，且石子数量为奇数，所以只要玩家每次都是先取石子，那么他总会胜出，因为他每一次都可以选择石子数量最多的那一组，那么到最后他的石子数量一定是最多的。

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

ps：6-14，6-15的题目都是二分法，这里不再赘述