纸牌博弈

Leetcode Link: 纸牌博弈__牛客网 (nowcoder.com)

题目讲解 https://www.bilibili.com/video/BV1ET4y1U7T6?p=7&t=144.7

题目

有一个整型数组 arr，代表数值不同的纸牌排成一条线。 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明，他们总会采用最优策略。请返回最后获胜者的分数。

从暴力递归到动态规划

暴力递归

分析：

为了便于分析，我们从一个玩家的视角对本题进行分析，即”我”

在每一轮（假设现在剩下的牌区间是 [L..R]，含两边），“我”只有两种情况：1) 该我了（先手）；2) 该对手（后手）

1. 在我先手的情况，我希望返回我能获得的最大分数，定义下面的先手函数f

   # 返回在[L..R]上先手时的最大分数，这分数我能决定，因为我绝顶聪明
   def f(arr, L, R):
   	# 先手时，如果只剩一张牌了，则必拿
   	if L == R:
   		return arr[L]
   	# 拿走一张牌后，就变成了在剩下的区间里后手操作, 故g为后手函数
   	p1 = arr[L] + g(arr, L+1, R)
   	p2 = arr[R] + g(arr, L, R-1)
   	# 我绝顶聪明，我一定会让自己的分数最大, 故返回max
   	return max(p1, p2)  

2. 在我后手的情况，我同样希望返回我能"获得"的最大分数。

然而，由于我是后手，故目前的主动权在对方手里。 而对方又绝顶聪明，所以他一定会让我拿到最小的分数

据此，定义后手函数 g

	# 返回在[L..R]上后手时的"最大分数"
	# 这分数我不能决定，因为我是后手，决定权在对方手里，而对方绝顶聪明
	def g(arr, L, R):
		# 后手时，只剩一个了，会被对方拿走，因此我只能得到0
		if L == R:   
			return 0
		# 对方取走arr[L]，那我就会变成在[L-1..R]上先手了
		p1 = f(arr, L+1, R)   
		# 对方取走arr[R]，那我就会变成在[L..R-1]上先手了
		p2 = f(arr, L, R-1)
		# 对方绝顶聪明，一定会给我最小的分数
		# 这不是我能决定的，因为主动权在对方手里，对方先手我后手
		return min(p1, p2)

最终，在一场游戏中，从一开始，一个玩家只能是先手或者后手 因此主函数为（这次要从上帝视角看了，毕竟这道题关注的是本场游戏能够返回的最大分数)

class Cards:
    def cardGame(self, arr):
	    if len(arr)==0: # 边界条件
		    return 0
		return max(f(arr, 0, len(arr)-1), g(arr, 0, len(arr)-1))

因此，最终的代码如下：

class Cards:
	# 主函数
    def cardGame(self, arr):
	    if len(arr)==0: # 边界条件
		    return 0
		xianshou = self.f(arr, 0, len(arr)-1)
		houshou = self.g(arr, 0, len(arr)-1)
		return max(xianshou, houshou)
		
	# 先手函数
	def f(self, arr, L, R):
		if L == R:
			return arr[L]
		p1 = arr[L] + self.g(arr, L+1, R)
		p2 = arr[R] + self.g(arr, L, R-1)
		return max(p1, p2)   
 
	# 后手函数
	def g(self, arr, L, R):
		if L == R:   
			return 0
		p1 = self.f(arr, L+1, R)   
		p2 = self.f(arr, L, R-1)
		return min(p1, p2)

记忆化搜索

从暴力递归到记忆化搜索，只需要画出调用栈的树状图，看看函数之间有没有重复就行了

class Cards:
	# 主函数
    def cardGame(self, arr):
	    if len(arr)==0: # 边界条件
		    return 0
		# 定义记忆，需要注意长度
		memof = [[-1 for _ in range(len(arr)+1)] for _ in range(len(arr)+1)]
		memog = [[-1 for _ in range(len(arr)+1)] for _ in range(len(arr)+1)] 
		xianshou = self.f(arr, memof, memog, 0, len(arr)-1)
		houshou = self.g(arr, memof, memog, 0, len(arr)-1)
		return max(xianshou, houshou)
		
	# 先手函数
	def f(self, arr, memof, memog, L, R):
		if L == R:
			return arr[L]
		
		if memof[L][R] != -1:
			return memof[L][R]
		else:
			p1 = arr[L] + self.g(arr, memof, memog, L+1, R)
			p2 = arr[R] + self.g(arr, memof, memog, L, R-1)
			res = max(p1, p2)
			memof[L][R] = res
		return res
 
	# 后手函数
	def g(self, arr, memof, memog, L, R):
		if L == R:   
			return 0
		if memog[L][R] != -1:
			return memog[L][R]
		else:
			p1 = self.f(arr, memof, memog, L+1, R)   
			p2 = self.f(arr, memof, memog, L, R-1)
			res = min(p1, p2)
			memog[L][R] = res
		return res

动态规划（无压缩）

前面的暴力递归和记忆化搜索，都是采用自顶向下的方式进行的。

想象一个树，我们是从上到下走的，然后再返回回去

动态规划是从下至上的，即先从基础的 base case 进入，然后逐渐到顶。

class Cards:
	# 主函数
    def cardGame(self, arr):
	    if len(arr)==0: # 边界条件
            return 0
        # 定义dp表，显然需要俩
       	dp_f = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]
        dp_g = [[-1 for _ in range(len(arr))] for _ in range(len(arr))] 
        # 初值填写
        for i in range(len(arr)):
            dp_g[i][i] = 0   
            dp_f[i][i] = arr[i]
        # 注意是往右推着对角线填写
        # 第一层循环是对角线偏移量，第二层是行数，两者不可调换顺序
        for j in range(1, len(arr)):
            for i in range(len(arr)):
                if i+j <= len(arr)-1:
                    dp_f[i][i+j] = max(arr[i]+dp_g[i+1][i+j], arr[i+j]+dp_g[i][i+j-1])
                    dp_g[i][i+j] = min(dp_f[i+1][i+j], dp_f[i][i+j-1])
        return max(dp_g[0][len(arr)-1],dp_f[0][len(arr)-1])

启发和联系