本文共 1879 字，大约阅读时间需要 6 分钟。

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

算法思想

博弈问题的前提一般都是在两个聪明人之间进行，编程描述这种游戏的一般方法是二维 dp 数组，数组中通过元组分别表示两人的最优决策。 令 dp(i, j) 为亚历克斯可以获得的最大分数，其中剩下的堆中的石子数是 piles[i], piles[i+1], …, piles[j]。 可以转化为对亚历克斯的分数（用双方石子数的差值描述）作衡量，亚历克斯选一堆，加上相应分数，李选一次，减去相应分数。 状态转移方程 其实这道题状态转移非常简单 dp【i】【j】= max（选最左边的一堆，选最右边的一堆） 那么状态转移方程可以写为： dp【i】【j】= max（dp【i+1】【j】+piles【i】，dp【i】【j-1】+piles【j】），亚历克斯选 dp【i】【j】= min（dp【i+1】【j】-piles【i】， dp【i】【j-1】-piles【j】），李选 也可以简化为 dp【i】【j】= max（-dp【i+1】【j】+piles【i】，-dp【i】【j-1】+piles【j】） { 其中 dp(i+1,j)表示对手相对于当前选手多出的石子，当前选手选择 piles[i]，所以当前选手相对于对手多出的石子为 piles[i]−dp(i+1,j)。同理对于 piles[j]−dp(i,j−1)) 。所以当前选手取两种情况中的最大值。 }

#include 
   
    int max(int a,int b){	if(a>b) return a;	else return b;}int min(int a,int b){	if(a>b) return b;	else return a;}bool stoneGame(int* piles, int pilesSize){	int dp[pilesSize+1][pilesSize+1];	for (int i = 0; i < pilesSize; i++)         for (int j = 0; j < pilesSize; j++)        dp[i][j] = 0;	for(int i = 0;i
    
     <= pilesSize; size++){        for(int i=0;i< pilesSize-1;i++){          int j=pilesSize-i-1;          dp[i][j]=max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);		} 	}	return dp[0][pilesSize-1]>0;}int main(){	int piles[20] = {5,17,19,1,15,19,11,9,6,5,11,7,12,12,2,14,3,6,18,3};	if(stoneGame(piles,20)) printf("亚历克斯赢\n");	else printf("李赢\n");		int piles2[4] = {5,3,4,5};	if(stoneGame(piles2,4)) printf("亚历克斯赢\n");	else printf("李赢\n");		int piles3[8] = {4,5,7,1,10,6,3,5};	if(stoneGame(piles3,8)) printf("亚历克斯赢\n");	else printf("李赢\n");	return 0;}
    
   

转载地址：http://dgqen.baihongyu.com/