算法思想：

用暴力递归的方法： f(i,j)： 表示如果arr[i…j]这个排列上的纸牌被绝顶聪明的人先拿，最终能够获得什么分数。 s(i,j)： 表示如果arr[i…j] 这个排列上的纸牌被绝顶聪明的人后拿，最终能获得什么分数。 在先拿的f(i,j)中： 1.如果i == j(只有一张纸牌)，会被先拿纸牌的人拿走，所以返回arr[i]或arr[j]; 2.如果i != j,先拿纸牌的人有两种选择，要么拿走arr[i],要么拿走arr[j];

  1. 如果拿走arr[i],剩下arr[i+1,j]。对于arr[i+1,j]的纸牌，当前玩家成了后拿的人，因此他后续能获得的分数为s(i+1,j)
  2. 如果拿走arr[j],那么剩下arr[i,j-1],当前玩家后续能获得的分数为s(i,j-1).
  3. 作为绝顶聪明的人，必然会在两种决策中选择最优的。所以返回max{arr[i]+s[i+1,j],arr[j]+s[i][j-1]} 在后拿的s(i,j)中： 1.如果i == j,后拿纸牌的人什么也拿不到，返回0 2.如果i!=j,玩家的对手会先拿纸牌。
  4. 对手要么先拿走a[i]，那么排列剩下arr[i+1,j],
  5. 要么先拿走arr[j],剩下arr[i,j-1]
  6. 对手也是绝顶聪明的人，所以也会把最差的情况留给玩家因此返回min{f(i+1,j),f(i,j-1)}
%%运行超时
#include<bits/stdc++.h>

using namespace std;

int s(int l,int r,int * arr);

int f(int l,int r,int * arr){
    if(l==r){
        return arr[l];
    }
    return max(arr[l]+s(l+1,r,arr),arr[r]+s(l,r-1,arr));
}

int s(int l,int r,int * arr){
    if(l==r){
        return 0;
    }
    return min(f(l+1,r,arr),f(l,r-1,arr));
}

int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;++i){
        cin>>arr[i];
    }
    int res=max(f(0,n-1,arr), s(0,n-1,arr));
    cout<<res<<endl;
}

动态规划其实就是根据自己列的递归方程来确定。和题目都已经无关了。根据递归改变的参数定义我们的二维表，参数只有i和j随着改变，所以我们定义(i,j)的二维表。i是从左拿的牌，j是从右拿的牌。我们要求的答案是（0，arr.size()-1），所以两张二维表中，要求出f(0,n-1)和s(0,n-1)作为答案。又因为i<=j，所以我们要二维表的右上半部分就可以了。

初始值： f(i,i)为arr[i] ，s(i,i)为0 （都是根据递归方程得出）

不同的是，根据递归函数，f[i][j]要依赖于s[i][j]表，s[i][j]要依赖于f[i][j]表。

转移方程： f[i][j] = max(arr[j] + s[i][j - 1],arr[i] + s[i + 1][j]); s[i][j] = min(f[i+1][j],f[i][j-1]);

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;++i){
        cin>>arr[i];
    }
    vector<vector<int>>f(n,vector<int>(n,0));
    vector<vector<int>>s(n,vector<int>(n,0));
    for(int i=n-1;i>=0;--i){
        f[i][i]=arr[i];
        for(int j=i+1;j<n;++j){
            f[i][j]=max(arr[j]+s[i][j-1],arr[i]+s[i+1][j]);
            s[i][j]=min(f[i+1][j],f[i][j-1]);
        }
    }
    cout<<max(f[0][n-1],s[0][n-1])<<endl;
}