博弈问题之石头游戏的动态规划解法
最近遇到这样一个问题：
你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1, 100, 3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。
其实这个问题有很多的变种，比如leetcode上的海盗分宝石问题，蓝桥杯里的和尚上楼梯问题等等，都是博弈问题的一种。今天就借这个机会，以石头游戏这个问题为例学习一下这类问题的动态规划解法。
1. 确定问题的状态
对于本问题而言，最重要的状态就是石头堆的情况了。因此当前石头堆数组的开始和结束索引就是本题的状态量。其次，当前时间轮到谁来选择也很重要，这就是问题的另一个状态，先后手。
2. 确定dp数组含义
对于这里博弈问题，如果想要用动态规划的方法来解决，最关键的就是要用dp数组记录下博弈双方各自的状态。根据前面的分析，我们可以用一个三维dp数组来记录本题的状态。为了方便起见，在解题时我定义了一个数据结构:
class Node:
def __init__(self, fir, sec):
self.fir = fir
self.sec = sec其本质上还是一个三维数组。因此dp数组就为一个二维数组，其含义为：dp[i] [j].fir表示在石头堆piles[i…j]的情况下，先手的人可以得到的最多分数，其他情况以此类推。
3. 写出状态转移方程
在本问题中，选择都很简单，只要选择石头堆两端最大的就可以了。因此问题的关键不是在选择上，而是如何表示出博弈双方都选择当前情况的最优解（两人轮流选择）的这种状态变化。
我们先分析先手：当现在面对石头堆piles[i…j]时，当然是选择max(piles[i], piles[j])，这一点很容易想到。假设我选择了piles[i], 那么当轮到后手选择的时候，此时的后手就相当于“先手”, 即: dp[i][j].sec=dp[i+1][j].fir, 而先手在这一轮就相当于“后手”，于是便有dp[i][j] = dp[i+1] [j].sec + piles[i]。其他情况也是类似。
到这里我们就遇到问题的难点了，我们之前一直都是在分析每种情况单独存在的状态转移，但是先手的选择会对后手有影响，所以最终应该如何表示博弈双方的轮流选择呢？
为了解决这个问题，充分表现出先手对后手产生的影响，我们选择分别计算出先手选了左端的情况和右端的情况，分开来进行分析，最终完成dp数组的推演。
4. base case
本题的base case 还是比较容易找到的，由于dp数组的定义，因此base case 就是当i==j时，此时先手一定得分为piles[i]，而后手一定得分为0。
5. 代码实现
到这里，问题的分析部分就结束了，下面给出石头游戏问题的代码实现：
class node:
def __init__(self, fir, sec):
self.fir = fir
self.fir = sec
def stoneGame(piles):
n = len(piles)
dp = [[node(0, 0)]*n for _ in range(n)]
for i in range(n):
dp[i][i].fir = piles[i]
dp[i][i].sec = 0
for i in range(1, n):
for j in range(n-i):
p = j
q = i+j
left = pile[p] + dp[p+1][q].sec
right = pile[q] + dp[p][q-1].sec
if left > right:
dp[p][q].fir = left
dp[p][q].sec = dp[p+1][q].fir
else:
dp[p][q].fir = right
dp[p][q].sec = dp[p][q+1].fir
return dp[0][n-1].fir - dp[0][n-1].sec小结
此类问题大多具有共性，最主要的问题在于如何设计dp数组来存储博弈双方的状态，以及如何来表示博弈双方轮流选择时对后续选择的影响的。只要能把握好这两点，一般的博弈问题按照这种动态规划的思路来解决就没有什么大的问题了。
