# 0877. 石子游戏

## 题目地址(877. 石子游戏)

<https://leetcode-cn.com/problems/stone-game/>

## 题目描述

```
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 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 。


提示：

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。
```

## 前置知识

* 动态规划

## 公司

* 阿里
* 字节

## 思路

由于 piles 是偶数的，并且 piles 的总和是奇数的。

因此 Alex`可以做到`要不拿的全部是奇数，要么全部是偶数。

举个例子： 比如 Alex 第一次先拿第一个

这里有两种情况：

1. Lee 如果拿了第二块（偶数），那么 Alex 继续拿第三块，以此类推。。。
2. Lee 如果拿了最后一块（偶数），那么 Alex 继续拿倒数第二块，以此类推。。。

因此 Alex`可以`做到只拿奇数或者偶数，只是他可以控制的，因此他要做的就是数一下，奇数加起来多还是偶数加起来多就好了。 奇数多就全部选奇数，偶数就全部选偶数。 Lee 是没有这种自由权的。

## 关键点解析

* 可以用 DP（动态规划）
* 可以从数学的角度去分析

## 代码

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

## 扩展

腾讯面试题：一共 100 只弓箭 你和你的对手共用。你们每次只能射出一支箭或者两支箭，射击交替进行，设计一个算法，保证自己获胜。

答案： 先手，剩下的是 3 的倍数就行（100-1=99），然后按照 3 的倍数射箭必赢。 比如你先拿了 1，剩下 99 个。 对手拿了 1，你就拿 2。这样持续 33 次就赢了。如果对手拿了 2 个，你就拿 1 个，这样持续 33 次你也是赢的。

> 这是一种典型的博弈问题， 你和对手交替进行，对手的行动影响你接下来的策略。 这算是一种最简单的博弈问题了


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/877.stone-game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.