10.2

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

给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
例如:
arr=[1,2,100,4]。
开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿了4之后玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101。
arr=[1,100,2]。
开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100。所以返回100。

思路及代码

暴力递归

设置2个递归函数，一个是先拿f，一个是后拿s
结果是看f先拿整体区域和s后拿整体区域的最大值

// 先拿时，[i,j]段获得钱数
public static int f(int[] arr, int i, int j) {
	//对于i=j，即只有一个元素，作为先拿者，一定会拿走
	if (i == j) {
		return arr[i];
	}
	// 面对[i,j]，先拿着只能取两端的值，然后后拿剩余的值
	// 因此先拿arr[i]后拿剩余i+1的部分s(arr, i + 1, j)
	// 先拿着一定会选取最大的拿走
	return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}

// 后拿时，[i,j]段获得钱数
public static int s(int[] arr, int i, int j) {
	//对于i=j，即只有一个元素，作为后拿者，一定拿不到，所以返回0
	if (i == j) {
		return 0;
	}
	//面对[i,j]，后拿着只能先拿除了两端以外的值，是先拿，因此是f(arr, i + 1, j)
	//但是在本次，拿不到两端值，因为先拿者已经拿走，故无arr[i]+f(arr, i + 1, j)
	//也没有arr[i+1]+f(arr, i + 1, j)，因为面对的区间是[i,j]要么拿边界，要么不拿
	//由于先拿的人选择是最大的，而总和是一定的，因此，后者只能是最小min
	return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}

public static int win1(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));
}

优化递归

f和s记录每个区间上的值

• f[i][j]表示先拿[i,j]区间上，能获得的最大值
• s[i][j]表示后拿[i,j]区间上，能获得的最大值

public static int win2(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	//f[i][j] 表示先拿的[i,j]的位置可以获得的最大钱数
	int[][] f = new int[arr.length][arr.length];
	int[][] s = new int[arr.length][arr.length];
	
	for (int j = 0; j < arr.length; j++) {
		//初始化，先拿者面对arr[j]一定会全部拿走，而后拿者只能拿走0
		f[j][j] = arr[j];
		s[j][j] = 0;
		//i=j-1而j必须以0开始，但不会报错，因为i >= 0
		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]);
}