范围上尝试的模型
给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
博弈论：双方玩家都不会在对方单独改变策略的情况下让对方获得最大收益
其它类似的零和博弈问题：鳄鱼吃人、海盗分金币、欧拉信封等等
package com.harrison.class12; public class Code07_CardsInLine { public static int f(int[] arr,int L,int R) { // 如果只剩下一张牌了，又是先手，那就直接拿走最后一张 if(L==R) { return arr[L]; } // 如果先手拿的是左边的牌，那么后手只能在[L+1,R]上拿牌 // 如果先手拿的是右边的牌，那么后手只能在[L,R-1]上拿牌 // 这两种情况下，先手肯定会只选择对自己最有利的方式，也就是返回最大值 return Math.max(arr[L]+s(arr, L+1, R), arr[R]+s(arr, L, R-1)); } 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)); } public static void main(String[] args) { int[] arr= {4,7,9,5}; System.out.println(f(arr, 0, 3)); System.out.println(s(arr, 0, 3)); } }
