题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832
题目大意：
两个人在玩一个游戏：
给你一行n个数字，每次只能从左端或者右端取一个或多个数字。
每个人的分值就是他们各自取得的数字之和。
假设两人都足够聪明，问先手最多能比后手多多少分。
解题思路：
其实题目意思就是先手最多能得到多少分。
设dp[l][r]是取完[l,r]的数字时先手能获得的最大分值，sum是[l,r]的数字之和。
那么可以得到状态转移方程：
dp[l][r]=max(dp[l][r]，sum-dp[i+1][r])，(l=<i<=r)
dp[l][r]=max(dp[l][r],sum-dp[l][i-1])，(l<=i<=r)
这里sum-子区间最优解的操作相当于取反，就是子区间的先手变成了后手，后手变成了先手的意思。
代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<cctype> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #include<vector> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<string> 13 #define lc(a) (a<<1) 14 #define rc(a) (a<<1|1) 15 #define MID(a,b) ((a+b)>>1) 16 #define fin(name) freopen(name,"r",stdin) 17 #define fout(name) freopen(name,"w",stdout) 18 #define clr(arr,val) memset(arr,val,sizeof(arr)) 19 #define _for(i,start,end) for(int i=start;i<=end;i++) 20 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); 21 using namespace std; 22 typedef long long LL; 23 const int N=1e3+5; 24 const int INF=0x3f3f3f3f; 25 const double eps=1e-10; 26 27 int a[N],dp[N][N]; 28 29 int solve(int l,int r){ 30 if(l>r) return 0; 31 if(dp[l][r]!=-INF) 32 return dp[l][r]; 33 int sum=a[r]-a[l-1]; 34 //从左端取 35 for(int i=l;i<=r;i++){ 36 dp[l][r]=max(dp[l][r],sum-solve(i+1,r)); 37 } 38 //从右端取 39 for(int i=r;i>=l;i--){ 40 dp[l][r]=max(dp[l][r],sum-solve(l,i-1)); 41 } 42 return dp[l][r]; 43 } 44 45 int main(){ 46 int n; 47 while(cin>>n&&n){ 48 for(int i=1;i<=n;i++){ 49 for(int j=1;j<=n;j++){ 50 dp[i][j]=-INF; 51 } 52 } 53 for(int i=1;i<=n;i++){ 54 cin>>a[i]; 55 dp[i][i]=a[i]; 56 a[i]+=a[i-1]; 57 } 58 solve(1,n); 59 cout<<2*dp[1][n]-a[n]<<endl; 60 } 61 return 0; 62 }
UVA 10891 Game of Sum（区间DP（记忆化搜索））
原文：https://www.cnblogs.com/fu3638/p/8910112.html