题目描述： 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 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) 是奇数。 方法1：动态规划 参考代码地址 主要思路： （1）这里使用的动态规划的数组为 vector<vector<pair<int,int>>> dp； （2）dp[ i ][ j ].first表示在从 i 到 j 颗石子中，先手可以取到的最大值，dp[ i ][ j ].second表示在从 i 到 j 颗石子中，后手可以取到的最大值； （3）则对于dp[ i ][ j ].first，可以从前或后两种方式取，若是取前边的，既第 i 个，则dp[ i ][ j ].first=piles[i]+dp[i+1][j].second，之所以加上dp[i+1][j].second，是因为先手取完第 i 个后，在剩下的i+1到j个石子的取法中，就只能作为后手来选择，故使用second，类型的，取后面的，既第 j 个，则dp[ i ][ j ].first=piles[ j ]+dp[i][j-1].second； （4）则对于p[ i ][ j ].second作为后手，当p[ i ][ j ].first先手取完第 i 个后，该后手就成为了剩下的i+1到j个石子的取法中的先手，故 dp[i][j].second=dp[i+1][j].first，类似的，当p[ i ][ j ].first先手取完第 j 个后，则dp[i][j].second=dp[i][j-1].first; （5）最后返回先手和后手的比较大小；
class Solution { public: bool stoneGame(vector<int>& piles) { vector<vector<pair<int,int>>> dp(piles.size(),vector<pair<int,int>>(piles.size())); //初始化 for(int i=0;i<piles.size();++i){ dp[i][i].first=piles[i]; dp[i][i].second=0; } //从后面的行向前面的行进行遍历 for(int i=piles.size()-2;i>=0;--i){ for(int j=i+1;j<piles.size();++j){ int choose_left=piles[i]+dp[i+1][j].second; int choose_right=piles[j]+dp[i][j-1].second; if(choose_left>=choose_right){ dp[i][j].first=choose_left; dp[i][j].second=dp[i+1][j].first; } else{ dp[i][j].first=choose_right; dp[i][j].second=dp[i][j-1].first; } } } return dp[0][piles.size()-1].first>dp[0][piles.size()-1].second; } };