硬币游戏算法[关闭]

来玩个游戏：

有 n 叠硬币排成一排。第 i 叠硬币由 d_i 个硬币组成。两名玩家：玩家 1、玩家 2 交替移动。玩家轮流只能拿走第一堆或最后一堆或两者。当没有剩余硬币时游戏结束。每个玩家都希望最终拥有尽可能多的硬币。玩家 1 开始。

我想知道算法（听起来像贪婪算法）来计算游戏结束时每个玩家在双方都发挥最佳状态时拥有多少硬币。

我不知道如何处理此类算法。只是猜测策略还是有某种方法可以推断出来？或者也许这个问题太奇怪而无法实现算法？

示例（硬币从第一个到第 n 个堆叠）：

1、100、1 - 玩家分别拥有 2 和 100 个硬币（不幸的是，第一个玩家只能拿走第一堆和最后一堆 - 第二个玩家总是拿走 100 个硬币）

1, 1, 100, 1, 1, 5 - 玩家分别拥有 8 和 101 个硬币（我认为这是在最佳游戏之后 - 首先取 5 和 1，然后第二次取 1 以防止玩家 1 拿走 100 个硬币。如果玩家 1在他的第一步中拿走少于 6 个硬币，他将永远少于 8 个硬币）。

我希望我已经足够详细地说明了问题。你同意这很有趣吗？ :) 有人可以帮忙吗？

添加到@Peter's动态规划解法：

我认为重现会类似于以下内容：

考虑到硬币堆的范围从A[i,..j]
Let, dp[i, j]表示玩家 1 可能获得的最高分数。然后，

dp[i, j] = MAX {
                MIN( dp[i+2, j], dp[i+1, j-1], dp[i+2, j-1]) + A[i], //Case when Player2 will try to make the most of it if Player1 picks ith coin.
                MIN( dp[i+1, j-1], dp[i, j-2], dp[i+1, j-2]) + A[j], //Case when Player2 will try to make the most of it if Player1 picks the jth coin.
                MIN( dp[i+2, j-1], dp[i+1, j-2], dp[i+2, j-2]) + A[i] + A[j] // Case when Player2 will try to make the most of it when Player1 picks both the ith and jth coins.
               }

因为只有 N^2 种可能的游戏状态。可以通过填充一个大小为N^2的dp表来实现。

对于 C++ 爱好者：

#include<iostream>
using namespace std;
int Solve(int A[], int N, int **dp, int i, int j){
        if(dp[i][j] != -1)
                return dp[i][j];
        if(j<i)
                return 0;
        else if(j==i)
                return A[i];
        else if( (j-i) == 1)
                return (A[i] + A[j]);
        else{
                int opt1 = min(Solve(A, N, dp, i+2, j), Solve(A, N, dp, i+1, j-1));
                opt1 = min(opt1, Solve(A, N, dp, i+2, j-1));
                int opt2 = min(Solve(A, N, dp, i+1, j-1), Solve(A, N, dp, i, j-2));
                opt2 = min(opt2, Solve(A, N, dp, i+1, j-2));
                int opt3 = min(Solve(A, N, dp, i+2, j-1), Solve(A, N, dp, i+1, j-2));
                opt3 = min(opt3, Solve(A, N, dp, i+2, j-2));
                int res = max(opt1+A[i], opt2+A[j]);
                res = max(res, opt3+A[i]+A[j]);
                dp[i][j] = res;
                return res;

        }
}
int main(){
        int N;
        int A[N];
        cin >> N;
        for(int i=0; i<N; ++i)
                cin >> A[i];
        int **dp;
        dp = new int* [N];
        for(int i=0; i<N; ++i)
                dp[i] = new int[N];
        for(int i=0; i<N; ++i)
                for(int j=0; j<N; ++j)
                        dp[i][j] = -1;
        Solve(A, N, dp, 0, N-1);
        cout << dp[0][N-1] << endl;
        for(int i=0; i<N; ++i)
                delete [] dp[i];
        delete []dp;
        return 0;
}

另外，如@Peter指出你对第二个例子的分析是错误的。玩家 1 实际上有一个赢得 102 个硬币来赢得比赛的策略。