1.题目描述：点击打开链接
2.解题思路：本题是一道经典的利用递推式优化dp的题目，非常值得学习。首先，根据题意描述：不管怎么取，任何时刻的游戏状态都是原始序列的一段连续子序列，因此，我们想到用d(i,j)表示原序列的第i~j个元素的子序列（元素编号为1~n），在双方都采取最优策略的情况下，先手得分的最大值（只考虑i~j这些元素）。
状态转移时，我们需要枚举从左边取还是从右边取以及取多少个。这等价于给对方剩下怎样的子序列：是(k,j)，还是(i,k)(i≤k<j)。因此：
d(i,j)=sum(i,j)-min{d(i+1,j),d(i+2,j),…,d(j,j),d(i,j-1),d(i,j-2),…,d(i,i),0};
其中sum(i,j)是元素i到元素j的数之和。注意，这里的“0”是“取完所有数”的决策，有了它，方程就不需要显式的边界条件了。
两个人的得分之和是sum(1,n),因此答案是d(1,n)-{sum(1,n)-d(1,n)}=2*d(1,n)-sum(1,n)。注意，sum(i,j)的计算可以通过前缀和数组S得到。
下面谈一下重点部分：利用递推式来优化状态转移方程。
根据上述的写法，状态有O(n^2)个，每个状态又有O(n)个转移，因此时间复杂度为O(N^3)，空间复杂度为O(N^2)。对于本题的规模，，这样的复杂度已经够了。但是还可以进一步改进：
如果我们令f(i,j)=min{d(i+1,j),d(i+2,j),…,d(j,j)},g(i,j)=min{d(j,j),d(i,j-1),d(i,j-2),…,d(i,i)},则状态转移方程可以写为：
d(i,j)=sum(i,j)-min{f(i+1,j),g(i,j-1),0}
这里引入f和g函数的目的是因为它们均可以递推：f(i,j)=min{d(i,j),f(i+1,j)},g(i,j)={d(i,j),g(i,j-1)}（由定义即可得到该递推式）,因此每个f(i,j)的计算时间都降为O(1)。
下面给出两种不同写法的dp：先给出记忆化搜索的写法
（记忆化搜索写法）
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;typedef pair<long long, long long> PL;#define me(s) memset(s,0,sizeof(s))#define For(i,n) for(int i=0;i<(n);i++)const int N = 100 + 10;int S[N];int A[N];int d[N][N];int vis[N][N];int n;int dp(int i, int j){if (vis[i][j])return d[i][j];vis[i][j] = 1;int m = 0;//全部取光for (int k = i + 1; k <= j; k++)m = min(m, dp(k, j));for (int k = i; k < j; k++)m = min(m, dp(i, k));d[i][j] = S[j] – S[i – 1] – m;//如果i从0开始编号，这里要判断一下是否有i==0return d[i][j];}int main(){//freopen("t.txt", "r", stdin);while (~scanf("%d", &n) && n){S[0] = 0;for (int i = 1; i <= n; i++){scanf("%d", &A[i]);S[i] = S[i – 1] + A[i];}me(vis);//注意一定要清空printf("%d\n", 2 * dp(1, n) – S[n]);}return 0;}
（递推写法）
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;typedef pair<long long, long long> PL;#define me(s) memset(s,0,sizeof(s))#define For(i,n) for(int i=0;i<(n);i++)const int N = 100 + 10;int S[N];int A[N];int d[N][N];int f[N][N], g[N][N];int vis[N][N];int n;int main(){//freopen("t.txt", "r", stdin);while (~scanf("%d", &n) && n){S[0] = 0;for (int i = 1; i <= n; i++){scanf("%d", &A[i]);S[i] = S[i – 1] + A[i];}me(vis);for (int i = 1; i <= n; i++)f[i][i] = g[i][i] = d[i][i] = A[i];//边界for (int L = 1; L < n; L++)//按照L=j-i递增的顺序写for (int i = 1; i + L <= n; i++){int j = i + L;int m = 0;//注意此处，因为m=min{f(i+1,j),g(i,j-1),0}m = min(m, f[i + 1][j]);m = min(m, g[i][j – 1]);d[i][j] = S[j] – S[i – 1] – m;f[i][j] = min(d[i][j], f[i + 1][j]);//递推f和gg[i][j] = min(d[i][j], g[i][j – 1]);}printf("%d\n", 2 * d[1][n] – S[n]);}return 0;}
走走停停，不要害怕错过什么，
