题目： 877.石子游戏

题面

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子， 排成一行 ；每堆都有正整数颗石子，数目为 piles[i] 。

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

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

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例

示例 1：

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

示例 2：

输入：piles = [3,7,2,3]
输出：true

Tips

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

Code

代码解释

这段 C++ 代码实现了 “石头游戏” 问题的动态规划解决方案。通过一个一维动态规划数组 dp 来记录在不同的石头区间内先手玩家（Alex）与后手玩家（Lee）之间的最大分数差异。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int length = piles.size();  // 获取石头堆的数量
        auto dp = vector<int>(length);  // 初始化一个一维动态规划数组 dp，大小为 length
  
        // 初始化 dp 数组，使得每个位置 dp[i] 代表在只有一堆石头时先手玩家能得到的分数
        for (int i = 0; i < length; i++) {
            dp[i] = piles[i];
        }
  
        // 逆序遍历石头堆，计算不同区间内先手玩家可以获得的最大分数差异
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                // dp[j] 表示从第 i 堆到第 j 堆石头时，先手玩家的最佳选择
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]);
            }
        }
  
        // 如果 dp[length - 1] > 0，说明先手玩家总能获得比后手玩家更多的石头
        return dp[length - 1] > 0;
    }
};

逐行解释

int length = piles.size();:
- 获取石头堆的数量，并存储在 length 变量中。
auto dp = vector<int>(length);:
- 初始化一个大小为 length 的一维动态规划数组 dp，用来存储从第 i 堆到第 j 堆石头时，先手玩家可以获得的最大分数差异。
for (int i = 0; i < length; i++) { dp[i] = piles[i]; }:
- 遍历 piles 数组，将每个位置 i 的石头数量 piles[i] 赋值给 dp[i]。这意味着在只有一个堆石头时，先手玩家能获得的分数就是这堆石头的数量。
for (int i = length - 2; i >= 0; i--) { ... }:
- 从倒数第二堆石头开始，逆序遍历 piles 数组，目的是计算在不同区间内先手玩家的最佳选择。
for (int j = i + 1; j < length; j++) { ... }:
- 遍历从 i 到 j 的石头堆，计算在这个区间内先手玩家能获得的最大分数差异。
dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]);:
- 通过比较先手玩家在两种选择下能获得的最大分数差异来更新 dp[j]：
  - 选择拿走第 i 堆石头，剩余的区间为 [i+1, j]，此时后手玩家先手，分数差为 piles[i] - dp[j]。
  - 选择拿走第 j 堆石头，剩余的区间为 [i, j-1]，此时后手玩家先手，分数差为 piles[j] - dp[j - 1]。
return dp[length - 1] > 0;:
- 最后判断从第一堆到最后一堆石头的分数差 dp[length - 1] 是否大于 0。如果是，说明先手玩家可以确保自己获胜，返回 true。