877.石子游戏

链接：877.石子游戏
难度：Medium
标签：数组、数学、动态规划、博弈
简介：亚历克斯和李用几堆石子在做游戏。假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

题解 1 - typescript

• 编辑时间：2021-06-16
• 执行用时：104ms
• 内存消耗：44.8MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/stone-game/solution/shi-zi-you-xi-by-leetcode-solution/)。

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

题解 2 - typescript

• 编辑时间：2021-06-16
• 执行用时：84ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/stone-game/solution/shi-zi-you-xi-by-leetcode-solution/)。

function stoneGame(piles: number[]): boolean {
  return true;
}