python|博弈游戏01——拿纸牌算法|python|数据结构|递归|回溯

题目描述给定一个整型数组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。
解题思路（1）递归问题为了方便进行理解，可以列举出递归的整个过程
（2）设输入的arr为[1, 8, 10, 6]
（3）用win函数去求arr的最优解法，即在先手和后手中取最优解
（4）其中0和3代表数组前值与后值的双指针

>>>win([1, 8, 10, 6], 4) max(f([1, 8, 10, 6], 0, 3), s([1, 8, 10, 6], 0, 3))

（5）对于先手f函数，解析为取左边，或者取右边，使得自己结果最大，可以转换为，

>>>f([1, 8, 10, 6], 0, 3) max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2))

（6）对后后手s函数，解析为取左边，或者取右边，使得对手结果最小，可以转换为

>>>s([1, 8, 10, 6], 0, 3) min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2))

（7）同理，1，3代表了取走了左边的牌，0，2代表取走了右边的牌

>>>1 + s([1, 8, 10, 6], 1, 3) 1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2))>>>6 + s([1, 8, 10, 6], 0, 2) 6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1))>>>f([1, 8, 10, 6], 1, 3) max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2))>>>f([1, 8, 10, 6], 0, 2) max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1))

（8）进一步往下进行列举

>>>f([1, 8, 10, 6], 2, 3) max(10 + s([1, 8, 10, 6], 3, 3), 6 + s([1, 8, 10, 6], 2, 2)) max(10, 6) 10>>>f([1, 8, 10, 6], 1, 2) max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1)) max(8, 10) 10>>>f([1, 8, 10, 6], 1, 2) max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1)) max(8, 10) 10>>>f([1, 8, 10, 6], 0, 1) max(1 + s([1, 8, 10, 6], 0, 0), 8 + s([1, 8, 10, 6], 1, 1)) max(1, 8) 8>>>s([1, 8, 10, 6], 2, 3) min(f([1, 8, 10, 6], 3, 3), f([1, 8, 10, 6], 2, 2)) min(6, 10) 6>>>s([1, 8, 10, 6], 1, 2) min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1)) min(10, 8) 8>>>s([1, 8, 10, 6], 1, 2) min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1)) min(10, 8) 8>>>s([1, 8, 10, 6], 0, 1) min(f([1, 8, 10, 6], 1, 1), f([1, 8, 10, 6], 0, 0)) min(8, 1) 1

（9）回到第（7）计算结果

>>> 1 + s([1, 8, 10, 6], 1, 3) 1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2)) 1 + min(10, 10) 11>>> 6 + s([1, 8, 10, 6], 0, 2) 6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1)) 6 + min(10, 8) 14>>> f([1, 8, 10, 6], 1, 3) max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2)) max(14, 14) 14>>> f([1, 8, 10, 6], 0, 2) max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1)) max(9, 11) 11

（10）回到第（5）步

>>>f([1, 8, 10, 6], 0, 3) max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2)) max(11, 14) 14

（11）回到第（6）步

>>>s([1, 8, 10, 6], 0, 3) min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2)) min(14, 11) 11

【python|博弈游戏01——拿纸牌】（12）因此最优分数方案为先手拿牌，先取6再取8，分数为14，后手方案只能取10和1，分数为11
代码

def win(arr, sz): if sz == 0: return 0 else: return max(f(arr, 0, sz - 1), s(arr, 0, sz - 1))#先手 def f(arr, i, j): if i == j: return arr[i] else: return max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1))#后手 def s(arr, i, j): if i==j:#表示先手拿过了，只剩下一个的局面 return 0 else: return min(f(arr, i + 1, j), f(arr, i, j - 1))#先手想赢，后手就需要拿最不好的if __name__=="__main__": arr = [1, 8, 10, 6] print(win(arr, len(arr)))