排成一条线的纸牌博弈问题

给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左和最右的纸牌，玩家A和玩家B绝顶聪明。请返回最后的获胜者的分数。

输入描述:
输出包括两行，第一行一个整数n，代表数组arr长度，第二行包含n个整数，第i个代表arr[i]。

输出描述:
输出一个整数，代表最后获胜者的分数。

示例1

输入

4
1 2 100 4

输出

101

暴力递归

import java.util.Scanner;

public class Card {
	public static int win(int[] card,int n) {
		if(card==null)return 0;
		return Math.max(f(card,0,n-1), s(card,0,n-1));
	}
	public static int f(int[] card,int L,int R) {//先手,从L到R区间拿牌
		if(L==R) {//只剩一张牌，先手只能拿这一张牌
			return card[L];
		}
		//否则，先手有两种选择：
		//(1)拿card[L]
		//(2)拿card[R]
		return Math.max(card[L]+s(card,L+1,R),card[R]+s(card,L,R-1));
	}
	public static int s(int[] card,int L,int R) {//后手,从L到R区间拿牌
		if(L==R) {//只剩一张牌，后手等先手拿完后，一张牌都不剩了
			return 0;
		}
		//先手会使后手的拿牌最差
		return Math.min(f(card,L,R-1), f(card,L+1,R));
	}
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int[] card=new int[n];
		for(int i=0;i 

 动态规划
 
从暴力递归改动态规划
 
card={3,5,2,1,0}
 
可变参数是取牌区间左限L和右限R 变化范围 是 0~4（card.length-1）
 
二维数组 f [5] [5]、 s [5] [5]
 
初始化：
 f 表和 s 表对角线下侧不需要填（因为L >= R）;
 
对角线上：
 
		if(L==R) {//只剩一张牌，先手只能拿这一张牌
			return card[L];
		}
 
对于 f 表，填上card[i]的值；
 
	if(L==R) {//只剩一张牌，后手等先手拿完后，一张牌都不剩了
			return 0;
	}
 
对于 s 表，都填上0；
 
状态转移方程：
 对于 f 表：
 
return Math.max(card[L]+s(card,L+1,R),card[R]+s(card,L,R-1));
 
max ( card [ L ] + s [ L + 1 ] [ R ] , card [ R ] + s [ L ] [ R - 1 ] )
 
对于 s 表
 
return Math.min(f(card,L,R-1), f(card,L+1,R));
 
min ( f [ L ] [ R - 1 ] , f [ L + 1 ] [ R ] )
 
下面完成填表工作：
 
 
 
最终的结果是 max ( f [ 0 ] [ 4 ] , s [ 0 ] [ 4 ] ) , 表中 标红 的格子。
 
import java.util.Scanner;

public class Card {
	
	public static int dp(int[] card) {
		int N=card.length;
		int[][] f=new int[N][N];
		int[][] s=new int[N][N];
		for(int i=0;i