有n枚硬币按照0到n-1对它们进行编号，其中编号为i的硬币面

#include<stdio.h>
#include<memory.h>
#define N 100
int v[N];
int maxValue[N][N];
int select[N][N];
int MaxValue(int v[],int n);
int main(){
    int n;
    while(EOF != scanf("%d", &n)){
        for(int i = 0; i < n; i++){
            scanf("%d", &v[i]);
        }
        printf("%d", MaxValue(v, n));
    }
}
int MaxValue(int v[], int n){
    int i, j, len;
    for(i = 0; i < n; i++)
        maxValue[i][i] = v[i];
        select[i][i] = i;
    for(i = 0; i < n - 1; i++){
        if(v[i] > v[i + 1]){
            maxValue[i][i + 1] = v[i];
            select[i][i + 1] = i;
        }
        else{
            maxValue[i][i + 1] = v[i + 1];
            select[i][i + 1] = i + 1;
        }
    }
    for(len = 3; len <= n; len++){
        for(i = 0; i < n - len + 1; i++){
            j = i + len - 1;
            int first, last;
            if(select[i + 1][j] == j)
                first = v[i] + maxValue[i + 1][j - 1];
            else if(select[i + 1][j] == i + 1)
                first = v[i] + maxValue[i + 2][j];
            if(select[i][j - 1] == i)
                last = maxValue[i + 1][j - 1] + v[j];
            else if(select[i][j - 1] == j - 1)
                last = maxValue[i][j - 2] + v[j];
            if(first > last){
                maxValue[i][j] = first;
                select[i][j] = i;
            }
            else{
                maxValue[i][j] = last;
                select[i][j] = j;
            }
        }
    }
    return maxValue[0][n - 1];
}

#include<iostream>
#include<vector>
using namespace std;

int MaxValue(int v[], int n)
{
	
	vector<vector<int>> dp(n, vector<int>(n, 0));  //dp[i][j]表示在还剩v[i]~v[j]时，先拿的人可以最多拿多少钱
	vector<vector<int>> record(n, vector<int>(n, 0));  //record[i][j]记录在还剩v[i]~v[j]时，先拿的人选择了哪一个 只有i和j两种可能
	for(int i = 0; i < n; i++)
	{
		dp[i][i] = v[i];
		record[i][i] = i;
	}

	for(int i = 2; i <= n; i++) //当前剩余硬币数量遍历
	{
		for(int s = 0; (s + i) <= n; s++) //起始位置遍历
		{
			int e = i + s - 1; //当前结束位置
			int num1 = v[s], num2 = v[e];
			
			if(i >= 3) //长度超过2的时候需要考虑剩下的硬币中能拿到的最多的钱数
			{
				//假设拿第一个
				if(record[s + 1][e] == s + 1) //第二个人会拿剩下的里面的第一个
					num1 += dp[s + 2][e];
				else                          //第二个人会拿剩下的里面的最后一个
					num1 += dp[s + 1][e - 1];

				//假设拿最后一个
				if(record[s][e - 1] == s) 
					num2 += dp[s + 1][e - 1];
				else
					num2 += dp[s][e - 2];
			}

			record[s][e] = (num1 > num2) ? s : e;
			dp[s][e] = (num1 > num2) ? num1 : num2;
		}
	}
	return dp[0][n - 1];
}

int MaxValue(int v[], const int len) {
	int r[100][100], s[100][100];  
	int n = len - 1;
	for (int i = 0; i < len; i++) {
		r[i][i] = v[i];
		s[i][i] = v[i];
	}
	for (int i = len - 2; i >= 0; i--) {
		for (int j = i + 1; j < len; j++) {
			int sum = s[i][j] = v[i] + s[i + 1][j];
			r[i][j] = max(sum - r[i + 1][j], sum - r[i][j - 1]);
		}
	}
	return r[0][len - 1];
}

//对这个题目理解好像有点不很清楚，个人觉得，偶数奇数的话，好像没有影响。。。请大家指正。
//第一种，是两者都想要最后得到最大的和，所以第一个人有两种选择，取得第一个数剩下的由第二个人取或者取得最后一个数剩下的由第二个人取，这两种方案取最大值。而第二个人取得时候，要使得第一个人取得的数最小。
//代码如下：


public class themaxcone {
    public static void  main(String[]args)
    {
        //int v[] = {3,6,0,1,4,7,9,2,6,8}; //24
        //int v[] = {3,6,7,0,2,5};  //14
        //int[]v = {1,1,1,1,0,1,1,1,1};  //4
        int []v = {5,3,4};  //8

        int max = MaxValue(v, v.length);
        System.out.println(max);
    }

    private static int MaxValue(int[] v, int n) {
        int sum = 0;
        for(int i=0;i<n;i++)
        {
            sum +=v[i];
        }
        int max = thefirstone(v, 0,n-1);
        return max;   //>sum-max?max:sum-max;
    }

    private static int thefirstone(int[] v, int start, int end) {

        if (start == end)
            return v[start];
        if(start<end) {

            return Math.max(v[start] + thesecondone(v, start + 1, end),
                    v[end] + thesecondone(v, start, end - 1));
        }
        return 0;
    }

    private static int thesecondone(int[] v, int i, int end) {
        return Math.min(thefirstone(v,i+1, end), thefirstone(v,i,end-1));
    }
}


//第二种的话，如果只需要保证第一个人取得的数最大，第二个人要尽量使得第一个人的最后所得和最大，这种理解只需要把thesecondone函数中return Math.max(thefirstone(v,i+1, end), thefirstone(v,i,end-1));的min改为max。


//大家的思路：
//这个问题需要再加一个条件：
// n为偶数，应为如果n为偶数，先拿的必胜，如果n为奇数，那么先拿的必输。
//  思路：假设n为偶数，那么先拿的可以决定后拿每次拿的硬币在原硬币位置中下标为奇数或者为偶数，
// 那么先拿的可以比较硬币在奇数位置的面额之和 和 偶数位置的面额之和，从而使得自己每次拿奇数还是偶数。

	
	

		int getMax(int v[], int left, int right){
	

	

		    // 当前硬币编号 left, right, 采取最有策略使得最终面额最大
	

	

		    if(left==right){
	

	

		        return v[left];
	

	

		    }
	

	

		    int get_left = getMax(v, left+1, right);
	

	

		    int get_right = getMax(v, left, right-1);
	

	

		    int get_cur = get_left > get_right ? get_right : get_left; // 减少对方的收益
	

	

		    int sum = 0;
	

	

		    for(int i=left; i<=right;i++){
	

	

		        sum += v[i];
	

	

		    }
	

	

		    return sum-get_cur;
	

	

		}
	

	

		
	

	

		int maxValue(int v[], int n){
	

	

		    return getMax(v, 0, n-1);
	

	

		}
	

/*区间dp？？？*/
int MaxValue(int v[],int n)
{
    for(int i=1;i<=n;i++)
        dp[i][i] = v[i];
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
            //区间dp
            dp[i][j] = max(dp[i+1][j]+v[i],dp[i][j-1]+v[j]);
    }
    return dp[1][n];
}

/* 是我想的太简单了吗？我觉得应该先确定奇偶。
如果是偶数个的话，第一个人可以控制第二个人的选择是在奇数列还是偶数列。
如果是奇数个的话就只能选最大的了*/
int Max_Value(int a[], int n)
{
    int i;
    int max_value_a = 0;
    int max_value_b = 0;

    if(n % 2 == 0)
    {
        for(i = 0; i < n; i++)
	{
	    if(i % 2 == 0)
	    {
	        max_value_a += a[i];
	    }
	    else
	    {
	        max_value_b += a[i];
	    }
	}

	return max_value_a > max_value_b ? max_value_a : max_value_b;
    }
    else
    {
        if(a[0] > a[n - 1])
	{
	    for(i = 1; i < n; i++)
	    {
	        if(i % 2 == 0)
		{
		    max_value_a += a[i];
		}
		else
		{
		    max_value_b += a[i];
		}
	    }

	    return max_value_a < max_value_b ?
	           max_value_a + a[0] : max_value_b + a[0];
	}
	else
	{
	    for(i = 0; i < n - 1; i++)
	    {
	        if(i % 2 == 0)
		{
		    max_value_a += a[i];
		}
		else
		{
		    max_value_b += a[i];
		}
	    }

	    return max_value_a < max_value_b ?
	           max_value_a + a[n - 1] : max_value_b + a[n - 1];
	}
    }
}

int MaxValue(int v[], int n)
{
	vector<vector<int>> sum(n,vector<int>(n)), dp=sum;
	for (int i = 0; i < n; i++)
		dp[i][i] = sum[i][i] = v[i];
	for (int i = n - 2; i >= 0; i--)
		for (int j = i + 1; j < n; j++)
		{
			sum[i][j] = sum[i][j - 1] + v[j];
			dp[i][j] =sum[i][j]-min(dp[i + 1][j],dp[i][j - 1]);
		}
	return dp[0][n - 1];
}

/*
 * 采用递归模拟先取和后取操作；
 *      先取：当只有一个时，直接取走；否则从剩下的左右两端分别尝试取走，并加上取走后，对于剩下的进行后取，两者中的最大值
 *      后取：当只有一个时，返回0，因为先取的不会给你留下；否则，就是作为 对手取走之后的 剩下串的 先取者，
 *            但是对手只会给你留下小的那部分。
 */

public static int maxValue(int[] v){
    return f(v, 0, v.length - 1);
}

public static int f(int[] v, int i, int j){
    if(i == j)
         return v[i];
   return Math.max(v[i] + s(i + 1, j), v[j] + s(i, j - 1));
}

public static int s(int[] v, int i, int j){
    if(i == j)
         return 0;
    return Math.min(f(v, i + 1, j), f(v, i, j - 1));
}

def maxpro(n,vi):
    dp=[[0 for i in xrange(n+1)] for j in xrange(n+1)]
    #设dp(i, j)表示两个人在序列ai, ai+1, ... aj上博弈时，先手可以拿到的最大价值。
    sum=[0 for i in xrange(n+1)]
    #sum(k)表示从数列开始(通常建议从1开始)到k位置的所有的元素的和
    for i in xrange(1,n+1):
        sum[i]=sum[i-1]+vi[i-1]
    for j in xrange(n):
        for i in xrange(1,n):
            if i+j<=n:
                dp[i][i+j]=sum[i+j]-sum[i-1]-min(dp[i+1][i+j],dp[i][i+j-1])
    print dp[1][n]

def choose(itemlist,my_stack,op_stack,turn,result,start,end,score):
	print turn,start,end
	if start>end:
		result.append(score)
	elif start==end:
		if turn==0:
			ano_score=score+itemlist[start]
			result.append(ano_score)
		else:
			result.append(score)
	else:
		if turn==0:
			my_stack.append(itemlist[start])
			ano_score=score+itemlist[start]
			# print '+++++++++++++++++++++++++++++++++++++++++++++++'
			choose(itemlist,my_stack,op_stack,1,result,start+1,end,ano_score)
			my_stack.pop()
			my_stack.append(itemlist[end])
			ano_score=score+itemlist[end]
			# print '----------------------------------------------'
			choose(itemlist,my_stack,op_stack,1,result,start,end-1,ano_score)
			my_stack.pop()
		else:
			op_stack.append(itemlist[start])
			# print '+++++++++++++++++++++++++++++++++++++++++++++++'
			choose(itemlist,my_stack,op_stack,0,result,start+1,end,score)
			op_stack.pop()
			op_stack.append(itemlist[end])
			# print '----------------------------------------------'
			choose(itemlist,my_stack,op_stack,0,result,start,end-1,score)
			op_stack.pop()
def MaxValue(v,n):
	if n==0:
		return 0
	if n==1:
		return v[0]
	else:
		presult=[]
		my_choose=[]
		op_choose=[]
		my_score=0
		my_turn=0
		start=0
		end=n-1
		choose(v,my_choose,op_choose,my_turn,presult,start,end,my_score)
		return max(presult)
if __name__ == '__main__':
	valueset=[4,6,9,2,5,3]
	print MaxValue(valueset,len(valueset))

	// 运用动态规划的思想



	// dp[i][j]:第i个到第j个序号的小球取，先取者能够取得的最优值



	// dp[i][j] = max(v[i]+sum[i+1,j]-dp[i+1][j], v[j]+sum[i,j-1]-dp[i][j-1])



	// 其中sum[i][j]为第i号球到第j号球的价值总和



	// 容易看出上述状态转移的时间复杂度为O(1)，按照区间从小到大的方向进行DP



	// 预处理出sum，因此总的时间复杂度为O(n^2)，其中n为小球的个数



	 



	#include <iostream>



	#include <algorithm>



	usingnamespacestd;



	constintmaxn = 1010;



	intdp[maxn][maxn], sum[maxn];



	intv[maxn];



	 



	intcal_sum(inti, intj) {



	    returnsum[j] - (i - 1 >= 0 ? sum[i-1] : 0);



	}



	 



	intmain() {



	 



	    intn;



	    while(scanf("%d", &n) != EOF) {



	        for(inti = 0; i < n; ++i) scanf("%d", &v[i]);



	        sum[0] = v[0];



	        for(inti = 1; i < n; ++i) {



	            sum[i] = sum[i-1] + v[i];



	        }



	        for(intl = 1; l < n; ++l) {



	            for(inti = 0; i + l < n; ++i) {



	                intj = i + l;



	                dp[i][j] = max(v[i]+cal_sum(i+1,j)-dp[i+1][j], v[j]+cal_sum(i,j-1)-dp[i][j-1]);



	            }



	        }



	        printf("%d\n", dp[0][n-1]);



	    }



	    return0;



	}

//典型博弈问题，左神有视频去看就知道了，这个答案是先取和后取都取最大值情况下获胜方是谁
public class 动态规划之博弈问题 {
	//递归版本
	public int  win(int [] arr) {
		if (arr==null||arr.length==0) {
			return 0;
		}
		return Math.max(f(arr,0,arr.length-1), s(arr,0,arr.length-1));
	}
    //后拿情况下的最大值
	private int s(int[] arr, int i, int j) {
		if (i==j) {
			return 0;
		}
		return Math.min(f(arr, i+1, j), f(arr, i, j-1));
	}
	//从 i 到j情况下拿到的值的最大值；
    //先拿情况下，等拿完之后就会变为后拿情况
	private int f(int[] arr, int i, int j) {
		if (i==j) {
			return arr[i];
		}
		//返回从i+1到j后拿情况+arr[i]和从i到j-1后拿情况下+arr[j]的两者取最大值就可以了
		return Math.max(arr[i]+s(arr, i+1, j), arr[j]+s(arr, i, j-1));
	}
	
	
	//动态规划版本
	public int  win2(int[] arr) {
		if (arr==null||arr.length==0) {
			return 0;
		}
		//首选从i-j中选出来的最大值
		int[][] f=new int[arr.length][arr.length];
		//次选从i-j选出来的最大值
		int[][] s=new int[arr.length][arr.length];
	    for (int j = 0; j < arr.length; j++) {
	    	//只有首选能选到的情况
			f[j][j]=arr[j];
			for (int i = j-1; i>=0; i--) {
				f[i][j]=Math.max(arr[i]+s[i+1][j], arr[j]+s[i][j-1]);
				s[i][j]=Math.min(f[i+1][j], f[i][j-1]);
			}
		}	
	    return Math.max(f[0][arr.length-1], s[0][arr.length-1]);
	}
}

/ * 方案：
 * 用自底向上的动态规划解决
 * r[i][j]记录硬币序列是i到j的子问题即先取的一方在i-->j个编号中能取到的最大值，s[i][j]记录i到j的总额 .则有
 * r[i][j] = max{v[i]+s[i+1][j]-r[i+1][j],v[j]+s[i][j-1]-r[i][j-1]}。
 * 关于r[i][j]：
 * （1）如果先取v[i]
 *    则先取方得到的最大值应该是当前v[i]加上剩余i+1-->j中所能取到的最大值（该最大值等于，在剩余硬币中，总额减去对方取的r[i+1][j],此时对方是先取方,即s[i+1][j]-r[i+1][j]）。
 * （2）如果先取v[j]
 *    则先取方得到的最大值应该是当前v[j]加上剩余i-->j-1中所能取到的最大值（该最大值等于，在剩余硬币中，总额减去对方取的r[i][j-1],此时对方是先取方，即s[i][j-1]-r[i][j-1]）。
 * @author wangsir
 *
 */
public static int maxValue(int v[]){
		int len=v.length;
		int[][] r=new int[len][len];
		int[][] s=new int[len][len];
		for(int i=0;i<len;i++){
			r[i][i]=v[i];
			s[i][i]=v[i];
		}
		for(int i=len-2;i>=0;i--){
			for(int j=i+1;j<len;j++){
				r[i][j]=Math.max(v[i]+s[i+1][j]-r[i+1][j], v[j]+s[i][j-1]-r[i][j-1]);
				s[i][j]=s[i+1][j]+v[i];
			}
		}
		return r[0][len-1];
	}

}
//先从大到小排序，之后间隔取值相加