纸牌博弈先手最优问题

纸牌博弈先手最优问题

问题描述:

一个纸牌明牌显示，牌上的数值就是分数:(就是一个数组，每个数均为非负整数），设置一个数为M，每个人都是绝顶聪明，都是按最优策略顺序拿牌，

一次可拿的牌数是大于等于1，小于等于M,问先手拿牌的人最多可以得几分。

答:这题使用贪心法绝对是不行的。

比如 1，1，1，100，设置M=2

那么第一个人绝对不能第一次拿两张牌，否则第二个人就可以拿到100.

这涉及到两个人博弈问题，但是博弈策略是一样的，所以可以使用同一个函数表示博弈策略

代码如下:
 

package DynamicAndRecursive;public class FirstMax {/*** * @param arr 纸牌数组* @param index 纸牌的有效首地址，也就是第一个人只能从index下标开始取* @param m 一次最多几张牌* @return 第一个人最多得分*/public static int firstMax(int[] arr, int index,int m){if(arr == null || arr.length == 0 || (index < 0) || index >= arr.length ){return 0;}int len = arr.length - index;//计算出数组剩余长度是否大于mint value = 0;if(len <= m){//如果数组长度小于m,那就全部拿过来，都是正数