纸牌博弈

	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];
	}
	
}

	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)，因为对于先拿后剩余的数组，当前人再拿的话是后拿的，然后取这两种拿法较大的分数。