leetcode 877 石子游戏

游戏描述：
总共偶数堆个石子堆piles[]，其中第 i 个石子堆有 piles[i]，Alex 和 李 两个玩家参与，每次只能从 数组的头部或者尾部拿取石子堆， 这些石子数总和为奇数 -> 肯定有输赢之分，alex 先拿， 假设两个人都是最佳策略，那么谁会赢？
alex 赢返回 true，李 赢返回 false。

游戏示例：

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

解法一： 动态规划
最佳路径类问题的感觉。
分析如下：
如果只剩下一堆石子，就只能取走当前的石子；如果剩下>1堆石子，那么就要从头部或者尾部取走石子，然后另一个玩家取走石子。-> 递归。以 alex 和 李 的 石子数量之差，如果最后总数 > 0 则 alex 赢，反之李赢。
二维数组 dp，行数和列数都为石子的堆数，dp[i][j] 代表 当剩下的石子堆为下标 i - j 时，两个玩家石子数之差的最大值，注意当前玩家不一定是先手 Alex。
其中 i <= j 时，剩下的石子堆才有意义，因此当 i > j 时，dp[i][j] = 0
当 i = j 时，只剩下一堆石子，当玩家只能取走这堆石子，因此对于所有 0 <= i < nums.length，都有 dp[i][j] = dp[i][i] = piles[i]
当 i < j 时，玩家可以选择取走 piles[i] 或者 piles[j]，在两种方案中，玩家可以选择 dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j - 1])

最后判断 dp[0][piles.length - 1] 的值。

var stoneGame = function(piles) {
    const length = piles.length;
    const dp = new Array(length).fill(0).map(() => new Array(length).fill(0));
    for (let i = 0; i < length; i++) {
        dp[i][i] = piles[i];
    }
    for (let i = length - 2; i >= 0; i--) {
        for (let 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;
};

优化

var stoneGame = function(piles) {
    const length = piles.length;
    const dp = new Array(length).fill(0);
    for (let i = 0; i < length; i++) {
        dp[i] = piles[i];
    }
    for (let i = length - 2; i >= 0; i--) {
        for (let j = i + 1; j < length; j++) {
            dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
        }
    }
    return dp[length - 1] > 0;
};

解法二：数学（脑筋急转弯??）
不管谁是先手，总有人会赢，那么赢的策略（组成堆）肯定是可以确定出来，并且两个玩家都是最佳策略，那么先手只要总是选择数量更多的一组石子就可以总赢。
其中 alex 是先手，那么返回 true。

var stoneGame = function(piles) {
    return true;
};

加油！！！！