877. 石子游戏

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解如果可以的话求个B站三连，感谢！

3、😊 分享一个阿秀自己私藏的黑科技网站，点此直达，主要是各类小众实用APP、网站等，除此外也包括高清影视、音乐、电视剧、AI、纪录片、英语四六级考试、考研考公、副业等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23/24/25届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载。

877. 石子游戏

力扣原题链接（点我直达）

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

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

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

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

Text Only

输入：[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) 是奇数。

第一版，看的解析，很厉害

https://leetcode-cn.com/problems/stone-game/solution/dong-tai-gui-hua-by-cliant/

动态规划+二维数组

判断的结果为先拿者是否可以拿到较多的石子。可以将问题转换为先拿者的石子数相对于后拿者的石子数的差值是否为正数，即表示先拿者的石子数是否多于后拿者的石子数。所以在依次拿石子的过程中，依次判断先拿者相对于后拿者的石子数即可。

不妨以 f(i,j)f(i,j) 表示对于下标 ii 到下标 jj 的 (j-i+1)(j−i+1) 堆石子，当前选手相对于对手能够多出的石子数。若 i==ji==j，则明显当前选手相对于对手多出的石子数为 f(i,j)=piles[i]f(i,j)=piles[i]，因为只有一堆石子。

若有两堆或多堆石子，则 f(i,j)=max(piles[i]-f(i+1,j), piles[j]-f(i,j-1))f(i,j)=max(piles[i]−f(i+1,j),piles[j]−f(i,j−1))，其中 f(i+1,j)f(i+1,j) 表示对手相对于当前选手多出的石子，当前选手选择 piles[i]piles[i]，所以当前选手相对于对手多出的石子为 piles[i]-f(i+1,j)piles[i]−f(i+1,j)。同理对于 piles[j]-f(i,j-1))piles[j]−f(i,j−1)) 。所以当前选手取两种情况中的最大值。

以 dp[i][j]dp[i][j] 二维数组存储 f(i,j)f(i,j) 的值，递推过程如下图所示：

因为初始情况只知道 i==ji==j ，即对角线上的 dpdp 值，所以推导 dpdp 数组按照红色序号顺序进行。

执行用时 :12 ms, 在所有 cpp 提交中击败了49.16%的用户

内存消耗 :17.1 MB, 在所有 cpp 提交中击败了20.00%的用户

C++
    bool stoneGame(vector<int>& piles) {
        //dp[i][j]为i开始到j结束alex能赢li多少分 alex先拿的话
       //dp[i][j] = max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1])(先拿左边的-对手比我多的，先拿右边的-对手比我多的)
    int len = piles.size();
    vector<vector<int>> dp (len,vector<int>(len,0));
    for (int i = 0; i < len; i++) {
        dp[i][i] = piles[i];
    }
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < len - i; j++) {
            dp[j][j + i] = max(piles[j] - dp[j + 1][j + i], piles[j + i] - dp[j][j + i - 1]);
        }
    }
    return dp[0][len - 1] > 0;

    }

降维处理

执行用时 :12 ms, 在所有 cpp 提交中击败了49.16%的用户

内存消耗 :8.2 MB, 在所有 cpp 提交中击败了96.80%的用户

C++
    bool stoneGame(vector<int>& piles) {
    int len = piles.size();
    vector<int> dp (piles);

    for (int i = 1; i < len; ++i)
        for (int j = 0; j < len - i; ++j)
            dp[j] = max(piles[j] - dp[j + 1], piles[j + i] - dp[j]);

    return dp[0] > 0;
    }
};