这是完美世界的一道笔试题，题目详述忘记了，大概记得这么一个意思：
给定一个数组nums[0~n-1];
A和B分变从数组的两端交替循环选择数据，累加到自身的积分中，并且A和B都采用最优策略选择数据，求最终A和B的积分。
首先考虑考虑用深度优先算法，定义一个函数int func(int st,int len)，这个函数的功能是仅考虑在数组剩余区间为[st,en]时刻及之后（之前各自的积分都重置为0），A和B的积分之差；
那么：
int func(int st,int len)
{
if(st>en) return 0;
if(st==en) return nums[st];
/*如果A选择最左端数据，那么B可以选择新的最左端或者最右端，B会选择二者中A本轮积分差和以后积分差之和最小的那种方式*/
int t1= min(nums[st]-nums[st+1]+func(st+2,en),nums[st]-nums[en]+func(st+1,en-1));
//同样的考虑A选择最右端数据的情况下B的选择
int t2 = min(nums[en]-nums[en-1]+func(st,en-2),nums[en]-nums[st]+func(st+1,en-1));
//A会选择两种情况下最优的那个
return max(t1,t2);
}【数组两端取数】上述采用的DFS方法，会有大量的重复计算，因为对每一个(st,en)都会重复多次进入到一个func(st,en)，而且栈深度会很深，极可能会超时,考虑func(st,en)的值仅与(st,en)相关，如果我们能在计算[st,en]区间上的func函数值（积分差）时已知区间[st+2,en],[st+1,en-1],[st,en-2]上的积分差值，则完全可以避免重复调用。这其实是可以做到的，采用动态规划的方法来计算区间上积分差值。如果我们倒过来看，先计算最后一轮A和B的积分差，当在不同区间上计算积分是，积分差不同，分别保存，然后后退到倒数第二轮，计算新的区间上的积分差。用dp[st][en]保存区间[st,en]上的值。最后一轮的区间长度可能是1，也可能是2。
代码如下：
#include
#include
using namespace std;
int nums[200];
int dp[200][200]={0};
int main()
{
int n;
cin>>n;
int sum=0;
for(int i=0;
i>nums[i];
sum+=nums[i];
}
int len=0;
//分n为奇偶分类讨论下初始情况，len是区间[st,en]的长度-1
if(n%2==1)
{
for(int i=0;
i 推荐阅读
- OJ|POJ 2686 Traveling by Stagecoach (状态压缩DP)
- LeetCode|LeetCode总结，位运算总结
- HihoCoder|hihoCoder 1040 : 矩形判断 计算几何
- SDUT|最长上升子序列（动态规划） SDUT