<题目链接>
题目大意：
两个人轮流从一个序列中取数，他们都面临同样的二选一决策：是拿走最左边的数，还是拿走最右边的数？问先手最多能够得到的分数是多少。
解题分析：
一道比较经典的DP，因为每次只能从数组的两端取走一个数，所以每次面对的数组都只可能是一段连续的子数组。我们不妨假设$dp[l][r]$表示对于数组$A[i]~A[j]$，先手能够获得的最多得分。于是状态的转移就不难得出了。
枚举所有区间：
$l==r$的时候，肯定是$dp[l][r]=arr[l]$
而对于其他区间大于1的情况，$dp[l][r]=max(dp[l][r],((sum[r]-sum[l-1])-min(dp[l+1][r],dp[l][r-1])))$
官方题解 >>>
递推DP
#include <bits/stdc++.h>
using namespace std; #define N int(1e3+5)
int n,dp[N][N],arr[N],sum[N]; int main(){
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)scanf("%d",&arr[i]),sum[i]=sum[i-]+arr[i];
memset(dp,-0x3f,sizeof(dp));
for(int i=n;i>=;i--){
dp[i][i]=arr[i];
for(int j=i+;j<=n;j++){
dp[i][j]=max(dp[i][j],(sum[j]-sum[i-])-min(dp[i+][j],dp[i][j-]));
}
}
printf("%d\n",dp[][n]);
}
记忆化搜索
#include <bits/stdc++.h>
using namespace std; const int N = 1e3+;
int n,arr[N],dp[N][N],sum[N]; int DP(int l,int r){
if(l>r)return ;
if(dp[l][r]!=-)return dp[l][r];
dp[l][r]=-1e9;
if(l==r)dp[l][r]=arr[l];
else dp[l][r]=max(dp[l][r],(sum[r]-sum[l-])-min(DP(l+,r),DP(l,r-)));
return dp[l][r];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&arr[i]),sum[i]=sum[i-]+arr[i];
}
memset(dp,-,sizeof(dp));
printf("%d\n",DP(,n));
}