纸牌博弈

	public static int cardGame(int[] A, int n) {
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int i = 0; i < n; ++i) {
			f[i][i] = A[i];
		}
		f[A.length - 2][A.length - 1] = Math.max(A[A.length - 2], A[A.length - 1]);
		for (int i = f.length - 2; i >= 0; i--)
			for (int j = i + 1; j <= f.length - 1; ++j) {
				s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
				f[i][j] = Math.max(A[i] + s[i + 1][j], A[j] + s[i][j - 1]);
			}
		return Math.max(f[0][n - 1], s[0][n - 1]);
	}
      //递归版本简单，但会超时
	public static int cardGame(int[] A, int n) {
		int scorA = F(A, 0, n - 1);
		int scorB = S(A, 0, n - 1);
		return Math.max(scorA, scorB);
	}

	public static int F(int[] arr, int l, int r) {
		if (l == r)
			return arr[l];
		return Math.max(S(arr, l + 1, r) + arr[l], S(arr, l, r - 1) + arr[r]);
	}

	public static int S(int[] arr, int l, int r) {
		if (l == r)
			return 0;
		return Math.min(F(arr, l + 1, r), F(arr, l, r - 1));
	}

a和b都是绝顶聪明，他们每次拿元素时，肯定是按对自己最有力的方式拿。该题目先由最普通的递归解法，然后进行优化，到动态规划。

递归方式，对数组arr，元素数为n。

F(arr, l , r)表示对于数组arr，元素从l到r，先拿可以达到的最大分数；

S(arr, l, r)表示对于数组arr, 元素从l到r，后拿可以达到的最大分数。

对于F(arr, l, r)，先拿时，有两种拿法，拿第一个arr[l]，或最后一个arr[r]；如果拿arr[l]，那么剩余的arr[l+1,....r]能拿到的最大分数为S(arr, l+1, r)，分数为arr[l] +S(arr, l+1, r)； 如果拿arr[r]，剩余的arr[l, ...r-1]能拿到的最大分数为S(arr, l, r-1)，分数为arr[r] + S(arr, l, r-1)，因为对于先拿后剩余的数组，当前人再拿的话是后拿的，然后取这两种拿法较大的分数。

import java.util.Scanner;

public class Cards {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] A = new int[n];
			for (int i = 0; i < n; i++) {
				A[i] = scanner.nextInt();
			}
			System.out.println(cardGame(A, n));
		}
	}

	public static int cardGame(int[] A, int n) {
		// f[i][j]表示在牌[i...j]下，先选能获得的最大分数
		// s[i][j]表示在牌[i...j]下，后选能获得的最大分数
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int j = 0; j < n; j++) {
			f[j][j] = A[j];
			for (int i = j - 1; i >= 0; i--) {
				// 有两种拿法：1.先手拿最左边的。那么下一次拿的时候只能后选 2.先手拿最右边的。那么下一次拿的时候只能先选
				f[i][j] = Math.max(A[i] + s[i + 1][j], A[j] + s[i][j - 1]);
				s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]); // 后手只能获得较小的分数（双方都很聪明，后选当然只能获得较少的分数）
			}
		}
		return Math.max(f[0][n - 1], s[0][n - 1]);
	}
}

class Cards /// 记忆化搜索
{
public:
    const static int N = 303;
    int sum[N];
    int dp[N][N];
    int dfs(int l, int r, vector<int> A)
    {
        if (~dp[l][r]) return dp[l][r];
        if (l==r) return A[l];
        int ans = sum[r] - (l==0 ? 0 : sum[l-1]);
        ans -= min(dfs(l+1, r, A), dfs(l,r-1,A));
        return dp[l][r] = ans;
    }
    int cardGame(vector<int> A, int n)
    {
        sum[0] = A[0];
        for (int i=1;i<n-1;i++) sum[i]=sum[i-1] + A[i];
        memset(dp, -1, sizeof dp);
        return dfs(0, n-1, A);
    }
};
/**
考虑记忆化搜索，dp[l][r]表示l..r区间内取纸牌，先手的最大收益。
每个人要让自己收益最大，也就是让对手收益最小。
收益是l..r区间内所有纸牌的和 - 我取了之后剩下区间对手的收益。
*/

class Cards {
public:
    int cardGame(vector<int> A, int n) {
        vector<vector<int>> a(n+1,vector<int>(n,0));
        vector<vector<int>> b(n+1,vector<int>(n,0));
        a[0][0] = A[0];
        a[n-1][n-1] = A[n-1];
        
        for(int j=1;j<n;j++)
            for(int i=j;i>=0;i--)
            {
                a[i][j] = max(A[i]+b[i+1][j], A[j]+b[i][j-1]);
                b[i][j] = min(a[i+1][j], a[i][j-1]);             }                  return max(a[0][n-1], b[0][n-1]);
    }
};

import java.util.*;
/*这是一道很明显的动态规划题
用F[l][r]表示先选的人能拿到的最高分
用S[l][r]来表示后选的人能拿到的最高分
如对于一组从0,1,2，...,n-1的数
对于先选者，他有两种选法
若先选者选A[0],则对于后面的1，...,n-1数组，他就变成了后选者，此时能拿到的分为A[0]+S[1][n-1]
若先选者选A[n-1],则对于前面的数组0，...，n-2,同样变为后选者，此时能拿到得分为A[n-1]+S[0][n-2];
所以 F[0][n-1]=max(A[0]+S[1][n-1],A[n-1]+S[0][n-2])
对于后选者，他能能到的最高分是受先选者控制的，即他只能选到先选者留给他的最小值，将其转化为数学形式就是
S[l][r]=min(F[l+1][r],F[l][r-1]);
这里的最小值是先选者留给他的，他只能拿到最小值，打个比方，我是先选者，我若选A[0]，剩下的留给你选，这个时候主动权在你
所以你能得到的最大分必为F[1][n-1],我若选A[n-1]，剩下的留给你选，这个时候主动权在你
所以你能得到的分必为F[0][n-2],我肯定是要把能得到的分少的那个留给你，所以你只能得到Min(F[1][n-1],F[0][n-2]);
*/
public class Cards {
    public int cardGame(int[] A, int n) {
        int[][]F=new int [n][n];
        int [][]S=new int [n][n];
        for(int r=0;r<n;r++){
            F[r][r]=A[r];
            S[r][r]=0;
            for(int l=r-1;l>=0;l--){
                F[l][r]=Math.max(A[l]+S[l+1][r],A[r]+S[l][r-1]);
                S[l][r]=Math.min(F[l+1][r],F[l][r-1]);
            }
        }
        return Math.max(F[0][n-1],S[0][n-1]);
    }
}

import java.util.*;

public class Cards {
    public int cardGame(int[] arr, int n) {
        //f[i][j]表示我先选的情况下[i...j]能获得的分数
        //s[i][j]表示我后选的情况下[i...j]能获得的分数
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for (int j = 0; j < n; j++) {
            //先选得到的分数f[i][i]即为arr[i],此处隐藏了s[i][i]=0,由于默认值就是零，所以可以省略
			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][n-1],s[0][n-1]);
    }
}

class Cards {
public:
    int cardGame(vector<int> A, int n) {
        //dpFirst[i][j]表示从j开始长度i的纸牌序列里#先选#得分最高的
        //dpAfter[i][j]表示从j开始长度i的纸牌序列里#后选#得分最高的，
        vector<vector<int>> dpFirst(n,vector<int>(n)),dpAfter(n,vector<int>(n));
        for(int i=0;i<n;++i){
            dpFirst[0][i]=A[i];//只有一张牌的时候先选的人得此牌分数
            dpAfter[0][i]=0;//后选的人0分
        }
        for(int i=1;i<n;++i)
            for(int j=0;j<n-i;++j){
                int k=j+i;//k为序列终点
                //先选的人，若先选左边，则剩下的序列里他是后选者，先选右边同理
                dpFirst[i][j]=max(dpAfter[i-1][j]+A[k],dpAfter[i-1][j+1]+A[j]);
                //后选的人只能在先选者选了后，剩下的里面选最小的（因为先选者肯定采用最优策略）
                dpAfter[i][j]=min(dpFirst[i-1][j],dpFirst[i-1][j+1]);
                
            }
        return max(dpFirst[n-1][0],dpAfter[n-1][0]);
    }
};

# -*- coding:utf-8 -*-
#用first[j][i]表示先选的人能拿到的最高分,second[j][i]来表示后选的人能拿到的最高分
#对于先选者，他有两种选法
#1.若先选者选A[0],则对于后面的1，...,n-1数组，他就变成了后选者，此时能拿到的分为A[0]+S[1][n-1]
#2.若先选者选A[n-1],则对于前面的数组0，...，n-2,同样变为后选者，此时能拿到得分为A[n-1]+S[0][n-2];
#所以 F[0][n-1]=max(A[0]+S[1][n-1],A[n-1]+S[0][n-2])
#对于后选者，他能能到的最高分是受先选者控制的，即他只能选到先选者留给他的最小值，将其转化为数学形式就是
#S[l][r]=min(F[l+1][r],F[l][r-1])
#这里的最小值是先选者留给他的，他只能拿到最小值
class Cards:
    def cardGame(self, A, n):
        first=[[0 for i in range(n)] for i in range(n)]
        second=[[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            first[i][i]=A[i]
            second[i][i]=0
            j=i-1
            while j>=0:
                first[j][i]=max(second[j+1][i]+A[j],second[j][i-1]+A[i])
                second[j][i]=min(first[j+1][i],first[j][i-1])
                j-=1
        return max(first[0][n-1],second[0][n-1])

import java.util.*;

public class Cards {
    public int cardGame(int[] A, int n) {
        // write code here
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for(int i=0; i<n; i++){
            f[i][i]=A[i];
            for(int j=i-1; j>=0; j--){
                f[j][i]=Math.max(A[j]+s[j+1][i], A[i]+s[j][i-1]);
                s[j][i]=Math.min(f[j+1][i], f[j][i-1]);
            }
        }
        return Math.max(f[0][n-1], s[0][n-1]);
    }
}

def maxs(low,high,data):     if low == high-1:         return max(data[low],data[high])     else:         return max(data[low]+mins(low+1,high,data),data[high]+mins(low,high-1,data)) def mins(low,high,data):     if low == high-1:         return min(data[low],data[high])     else:         return min(maxs(low+1,high,data),maxs(low,high-1,data)) def main():     data = [1,5,3,4,7,2,6,3]     print(maxs(0,len(data)-1,data))

if __name__=="__main__":     main()  #来个python

}

	public static int cardGame(int[] A, int n) {
		// f[i][j]表示：在卡片是[i...j]时，此刻的后选者能获得的分数
		// s[i][j]表示：在卡片是[i...j]时，此刻的先选者能获得的分数
		// 如，f[3][6]表示剩余待取卡片范围是3到6时，此刻的先选者能获得的分数
		int[][] f = new int[n][n];
		int[][] s = new int[n][n];
		for (int j = 0; j < n; j++) {
		    // 当有 j+1 张卡片的时候，可以计算出：
			// 剩下只有第 j 张卡片时的情况，
			// 剩下第 j-1 到第 j 张卡片时的情况，
			// 剩下第 j-2 到第 j 张卡片时的情况，
			// ......
			// 剩下第 0 到第 j 张卡片时的情况。		
			// s[j][j] = 0; // 只有一张卡片时，后选者s[j][j] = 0；
			f[j][j] = A[j]; // 只有一张卡片时，先选者直接赋值即可。
			for (int i = j - 1; i >= 0 ; i--) {
				// 计算第 i 到第 j 张卡片时的情况，i = {j-1, j-2, ..., 0}
				// 计算先选者：
				// 本次选择完成后，在下次选择中变为后选者。
				// 分别判断选择最左和最右时的情况，使本次选择最优。
				// 选择最左第 i 张时，那下次就是第 i+1 到第 j 张卡片的后选者。
				// 选择最右第 j 张时，那下次就是第 i 到第 j+1 张卡片的后选者。
				// 比较两种选择方式，找到最优的结果。
				f[i][j] = Math.max(A[i] + s[i+1][j], A[j] + s[i][j-1]);
				// 计算后选者：
				// 本次先选者选完后，由本次的后选者选下一张牌，后选者是下一次的先选者。
				// 后选者本次不是实际进行拿牌，实际拿牌是下次以先选者的身份，所以计算后选者不用加上A[i]或A[j]。
				// 双方都很聪明，使后选者只能获取较小的分数。
				// 即，因为本次先选者的选择，使得后选者只能选择结果较小的分数
				s[i][j] = Math.min(f[i+1][j], f[i][j-1]);
			}
		}
		
		return Math.max(f[0][n-1], s[0][n-1]);
	}

昨晚听了左神将这题 今天试一下   import java.util.*;

public class Cards {
    

		/**
	 * @param arr
	 * @return
	 */
	public int cardGame(int[] arr, int n){
		
		if (arr == null || arr.length == 0) {
			return 0;
		}
		
		int sum = 0;
		for (int i : arr) {
			sum += i;
		}
		int firstVaule = first2(arr);
		return Math.max(firstVaule, sum - firstVaule);
	}
	
	public  int first2(int[] arr){
		int n = arr.length;
		int[][] first = new int[n][n];
		boolean odd = n % 2 == 1 ?  true: false;	//数组是否是奇数数组
		
		for (int i = 0; i < first.length; i++) {
			if (odd) {
				first[i][i] = arr[i];
			}
			
			for (int j = i - 1; j >= 0; j--) {
				if (odd ? (i +j) % 2 == 1 : (i +j) % 2 != 1 ) {
					first[i][j] = Math.min(first[i - 1][j], first[i][j + 1]);
				}else{
					first[i][j] = Math.max(arr[i] + first[i - 1][j], arr[j] + first[i][j + 1]);
				}
			}
		}
		
		return first[n - 1][0];
	}
	
}

        return int(max(first[0][n-1],second[0][n-1]))

/*经典DP了

最优子结构：
n张牌0,1,...,n-1;第一步
A作为先手要么拿第0张，要么拿第n-1张(原因是题目里说
只能从两端拿牌),拿了之后在剩下n-1张牌里A作为后手，
能获得最大得分， 也就是B作为先手在n-1张牌里得到大得分
后剩下多少分。 dp[i][j] = A[i]   //i==j  dp[i][j] = std::max(
            sum(A[i]...A[j]) - dp[i+1][j], //拿左边
            sum(A[i]...A[j]) - dp[i][j-1]) //拿右边 
         = sum(A[i]...A[j]) - std::min(dp[i+1][j], dp[i][j-1]
         = sum[j] - sum[i] + A[i] - std::min(dp[i+1][j], dp[i][j-1])
         (i<j)
为了方便计算，可以先计算好sum[i] = sum(A[0]...A[i]) 重叠子问题：
计算dp[i+1][j]与dp[i][j-1]都依赖子问题dp[i+1][j-1]，所以有重叠
子问题。

综上：动态规划可解。    
*/
class Cards {
public:
    int cardGame(vector<int> A, int n) {
        // write code here
        int i;
        for(i = 0; i < n; i++){
            dp[i][i] = A[i];
            if(i == 0) 
                sum[0] = A[i];
            else
                sum[i] = sum[i-1] + A[i];
        }
        
        for(int step = 2; step <= n; step++){
            for(i = 0; i <=n && i+step<=n; i++){
                int j = i+step-1;
                dp[i][j] = sum[j] - sum[i] + A[i] -
                           std::min(dp[i+1][j], dp[i][j-1]);
            }
            
        }
        return std::max(dp[0][n-1], sum[n-1] - dp[0][n-1]);
    }
    int dp[301][301];
    int sum[301];
};