数组两端取数

这是完美世界的一道笔试题，题目详述忘记了，大概记得这么一个意思：
给定一个数组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<iostream>
#include<algorithm>
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<n;++i)
    {
        cin>>nums[i];
        sum+=nums[i];
    }
    int len=0;
    //分n为奇偶分类讨论下初始情况，len是区间[st,en]的长度-1
    if(n%2==1) 
    {
        for(int i=0;i<n;++i)
            dp[i][i]=nums[i];
        len = 2; //倒数下一轮的区间长度
    }
    else
    {
        for(int i=0;i<n-1;++i)
        {
            dp[i][i+1] = max(nums[i],nums[i+1])-min(nums[i],nums[i+1]);
        }
        len =3;
    }
    while(len<n)
    {
        for(int i=0;i+len<n;++i)
        {
            dp[i][i+len]=max(min(nums[i]-nums[i+1]+dp[i+2][i+len],nums[i]-nums[i+len]+dp[i+1][i+len-1]),
                min(nums[i+len]-nums[i+len-1]+dp[i][i+len-2],nums[i+len]-nums[i]+dp[i+1][i+len-1]));
        }   
        len+=2;
    }
    cout<<(sum+dp[0][n-1])/2<<","<<(sum-dp[0][n-1])/2<<endl;
    return 0;
}