牛客算法直播题目总结Day1T1(零和博弈)

牛客上左程云(人称“左神”)的系列面试算法题串讲，到现在已经听了两课了，对第一课的知识进行总结。

题目1：

有一排正数，玩家A和玩家B都可以看到。每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。玩家A先拿，玩家B再拿，两人交替拿走所有的数字，两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。例如： 5，2，3，4 玩家A先拿，当前他只能拿走5或者4. 如果玩家A拿走5，那么剩下2，3，4.轮到玩家B，此时玩家B可以选择2或4中的一个。如果玩家A拿走4，那么剩下5，2，3.轮到玩家B，此时玩家B可以选择5或3中的一个。

实际是零和博弈题。此题可以分为先发与后发对过程进行描述，简单可以剖析为两步，后续进行递归，先发者肯定拿该数组中最大的数，而在剩下第二步中，只能担任的是后发者的身份。这么说有些抽象，具体用图例进行描述。原数组本为：

screenshot

若arr[] 数组的范围是i…j 则对于先发者f可操作的方式是。

screenshot

在i..j-1或者i+1..j之中，后发者会选择更大的数，则在这一数组中，第一次担任先发者的便只能变成后发者，这个思想很好地依赖了后发者的值，也使得整个递归可以相互依赖。则先发取到的数应该是第一个拿到的值加上第二步作为后发者得到的值，这是前两次拿数的过程。

而作为后发者，第一步没有拿值，在第二步中扮演先发者的角色。

在先发者和后发者的实现方法中，先发者应该返回的是以上两种情况的最大值，而后发者则是最小值，因为先发者是绝对理性的个体，他留给后发者肯定是比较小的。后发者的选择不是由自己选择的，而是由先发者留下最小的值进而来选。

则两方法实现为：

1 public static int f(int[] arr, int i, int j) { 2 if (i == j) { 3 return arr[i]; 4 } 5 return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1)); 6 } 7 8 public static int s(int[] arr, int i, int j) { 9 if (i == j) { 10 return 0; 11 } 12 return Math.min(f(arr, i + 1, j), f(arr, i, j - 1)); 13 } 14 }

其中，当i==j时，当数组中只剩下一个元素，若是作为先发者角色，返回该元素，当作为后发者，返回0. 注意，这里没有谁是一直作为先发者，谁一直是后发者的，每进行一步，该角色都在变化。

优化：若将递归数两者之间的依赖关系找出，可以得到如下递归数。

screenshot

先去和我妈看会儿电视两小时后过来写回来继续把它写完，最近打算看一本欧洲史，高中在跳蚤市场5元买的。上面可以发现f(1,5)递归了两次，如果数组的长度越大，就会有许多子过程是重复的。所以要进行优化。

优化一：将递归过程描述到两张表
根据上两个方法的内容，我们可以得到两张二维表，分别是f表和s表，用表的形式描述递归过程，则f表的对角线是数组中的每一个值，在先发者中，当i==j时，返回的值是arr[i]，这里可能有点难以抽象，首先要有的概念是任何角色都在某一步骤中担任先发者，因为递归过程类似一个个堆栈形成的递归树，每一个子过程一直细化下去，最终就是每一个i==j的过程时得到的值，那么代码后面实现的数据结构算法其实就是把数组细化成每一个元素再进行归并，则i..j就是整个需要被分治出的域，最终归并得到最大值。

screenshot

可以知道最终递归basics是对角线，所以可以利用两张表的值得到依次向上得到，最终需要的值是0~arr.length-1范围的值，这就有点类似于DP了。这种将无后效性的暴力递归(返回值和上一级查找下一级路径无关)都能通过将可变参数作为表索引改写成动态规划。知道对焦线，进行推算就一列一列往上遍历即可，代码体现为外层循环是列，内层循环是i=j-1，因为依次向上求，一直减为0，则所需要的值都会存在表中。

public static int win2(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int[][] f = new int[arr.length][arr.length];
	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]);
}

最后返回两张表右上角中最大的值。

优化二：只用一张表来描述

欲使用一张表来进行描述，需要对表进行分析，本来需要两张表依次得到值，如果对底层基准提供两步的值，则仅仅需要一张表。这里面一个条件是i==j时返回的值是对角线，另外再给一个条件是当i+1==j时候，(这里表示的是当数组中只有两个值的时候)，取最大的数作为返回值，则在表中可以表述成

screenshot

得到得是对角线(0,0)(1,1)(2,2)和(0,2).每次初始得base case得到两排得值，最后依次往上递归即可。两步之后的过程描述为

若选了i+1，则留下i+2..j或者i+1..j-1中的最小值

若选了j-1, 则留下i..j-2或者i+1..j-1中的最小值

最终代码为:

public static int p(int[] arr, int i, int j) {
	if (i == j) {
		return arr[i];
	}
	if (i + 1 == j) {
		return Math.max(arr[i], arr[j]);
	}
	return Math.max(arr[i] + Math.min(p(arr, i + 2, j), p(arr, i + 1, j - 1)),
			arr[j] + Math.min(p(arr, i + 1, j - 1), p(arr, i, j - 2)));
}

最后，需要对数据进行测试，要自己实现一个数据生成器:例如生成一个长度1-20的一个数组，数组中的数是1-20的数：

public static int[] generateRondomArray(){
	int [] arr = new int[(int)(Math.random()*20)+1];
	for(int i=0;i<arr.length-1;i++){
		arr[i] = (int)(Math.random()*20)+1;
	}
	return arr;
}

最终代码:

package problems_2017_07_18;

public class Problem_03_CardsInLine {

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

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

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

public static int win2(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int[][] f = new int[arr.length][arr.length];
	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]);
}

public static int win3(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
	}
	int scores = p(arr, 0, arr.length - 1);
	return Math.max(sum - scores, scores);
}

public static int p(int[] arr, int i, int j) {
	if (i == j) {
		return arr[i];
	}
	if (i + 1 == j) {
		return Math.max(arr[i], arr[j]);
	}
	return Math.max(arr[i] + Math.min(p(arr, i + 2, j), p(arr, i + 1, j - 1)),
			arr[j] + Math.min(p(arr, i + 1, j - 1), p(arr, i, j - 2)));
}

public static int win4(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	if (arr.length == 1) {
		return arr[0];
	}
	if (arr.length == 2) {
		return Math.max(arr[0], arr[1]);
	}
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
	}
	int[][] dp = new int[arr.length][arr.length];
	for (int i = 0; i < arr.length - 1; i++) {
		dp[i][i] = arr[i];
		dp[i][i + 1] = Math.max(arr[i], arr[i + 1]);
	}
	dp[arr.length - 1][arr.length - 1] = arr[arr.length - 1];
	for (int k = 2; k < arr.length; k++) {
		for (int j = k; j < arr.length; j++) {
			int i = j - k;
			dp[i][j] = Math.max(arr[i] + Math.min(dp[i + 2][j], dp[i + 1][j - 1]),
					arr[j] + Math.min(dp[i + 1][j - 1], dp[i][j - 2]));
		}
	}
	return Math.max(dp[0][arr.length - 1], sum - dp[0][arr.length - 1]);
}

public static int[] generateRondomArray() {
	int[] res = new int[(int) (Math.random() * 20) + 1];
	for (int i = 0; i < res.length; i++) {
		res[i] = (int) (Math.random() * 20) + 1;
	}
	return res;
}

public static void main(String[] args) {
	int testTime = 50000;
	boolean err = false;
	for (int i = 0; i < testTime; i++) {
		int[] arr = generateRondomArray();
		int r1 = win1(arr);
		int r2 = win2(arr);
		int r3 = win3(arr);
		int r4 = win4(arr);
		if (r1 != r2 || r1 != r3 || r1 != r4) {
			err = true;
		}
	}
	if (err) {
		System.out.println("2333333333");
	} else {
		System.out.println("6666666666");
	}
}

}
124

Enjoy Reading This Article?