题目大意：给你n个数，两个人轮流取，可以从左边开始去取连续的任意个，或者从右边取连续的任意个，

注意不能从两头取，所有的数都被取完游戏结束，输出先手与后手的分差；

解析：dp[i][j]   表示i~j区间内先手取的最大值，所以dp[1][n]表示的是取完所有数之后的最大值，

由于求的是最大值，所以给后手留下最小的，分两种情况，1.留给后手i+1~r区间；2.给后手留l~k区间

所以结果就是2*dp[i][j] - sum[n];

代码题解：

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn],sum[maxn],dp[102][102];
int n;
int vis[102][102];
int DP(int l,int r)
{
    if(vis[l][r])return dp[l][r];
    vis[l][r]=1;
    dp[l][r]=sum[r]-sum[l-1];
    for(int i=l;i<r;i++) //给后手留i+1~r区间
        dp[l][r]=max(dp[l][r],sum[r]-sum[l-1]-DP(i+1,r)); 
    for(int k=r-1;k>=l;k--)// 给后手留l~k区间
        dp[l][r]=max(dp[l][r],sum[r]-sum[l-1]-DP(l,k)); 
    return dp[l][r];
}
int main()
{

    while(scanf("%d",&n)&&n)
    {
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        printf("%d\n",2*DP(1,n)-sum[n]);
    }
    return 0;
}