877. Stone Game

石子游戏，偶数堆石子，一共奇数个石头，两个人只能从两端拿一堆，先拿的人可以取胜则返回true

动态规划

由于每次只能从行的开始或结束处取走整堆石子，因此可以保证整堆石子都是连续的。定义二维数组dp，行数和列数都等于石子的堆数，dp[i][j]表示当剩下的石子为下标 i 到 j 时，当前玩家与另一个玩家石子数量之差的最大值。

• 只有当i < j时，剩下的石子堆才有意义
• 只有当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[i][j]的值只和dp[i + 1][j] 与dp[i][j - 1]有关，只需要用到dp第 i 行和第 i + 1 行的值，使用一维数组代替二维数组，对空间进行优化。

• 时间复杂度 O(n^2)，空间复杂度O(1)
• Runtime: 80 ms, faster than 72.67%
• Memory Usage: 38.7 MB, less than 49.33%

/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
    let len = piles.length
    let dp = piles.slice()
    
    for (let i = len - 2; i >= 0; i--) {
        for (let j = i + 1; j <  len; j++) {
            dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1])
        }
    }
    
    return dp[len - 1] > 0
   
};

数学

假设有n 堆石子，n 是偶数，每堆石子的下标从 1 ~ n - 1，下标为偶数的石子堆属于第一组，下标为奇数的石子堆属于第二组，作为先手的人可以在第一次取走石子时就决定取走哪一组的石子，并全程取走同一组的石子。因此返回 true

• 时间复杂度 O(1)
• 空间复杂度O(1)
• Runtime: 80 ms, faster than 72.67%
• Memory Usage: 38.3 MB, less than 85.33%

/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
    return true
};