经典博弈问题的动态规划解法

问题

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

思路

如果一个问题可以分解成一个子问题，而子问题又可以分解成一个更小的子问题，那么我们就可以考虑用递归的方式来实现，比如斐波拉契数列。不过递归的方式有个严重问题就是会存在大量子问题额重复计算。动态规划也采用了类似的思路，不过和递归相反，是自底向上从子问题一步步计算到最终问题，通过额外的空间来记录状态，避免了子问题的重复计算，不过相比递归而言更难理解。

1.定义状态（最优子结构）

定义一个二维数组dp，dp[i,j]表示从第i堆到第j堆中最多可以拿到的石头数量(first,second)，first表示先手可以拿到的石头数量，second表示后手可以拿到的石头数量。题目说两个人都足够聪明，则2个人不管先手或者后手都以最先的方式去选择拿最左边或着最右边的石头堆。
数组每个位置表示在dp[i,j]中，先手可以拿到的石头数量和后手可以拿到的石头数量，那么我们最后要求解的就是dp[0,n]先手拿的是不是多过后手拿的。

2.状态转移

思考一下要求解dp[i,j]可否根据子问题来求解，答案是肯定的，我们要求dp[i,j]的2个值first和second。
先看dp[i,j].first如何求，先手可以有两个选择，拿左边或者右边
拿左边：获取石头数piles[i]，在剩下的石头堆中变成后手，即可以获得dp[i+1,j].second数量
拿右边：获取石头数piles[j]，在剩下的石头堆中变成后手，即可以获得dp[i,j-1].second数量
最优当然是哪种方式拿更多选哪个：即max(拿左边,拿右边)
再看dp[i,j].second
然而后手是没有选择的，先手选择了左边，那么后手在剩下的堆中就是先手，即dp[i+1,j].first，同理，先手选择了右边，则后手等于dp[i,j-1].first，即在先手选完后，后手在剩下的堆中先手最多能拿多少，这样一来我们要求解的问题都可以在前一轮已知的结果去推导，完全满足动态规划的解题思路。
那么最初的状态应该是什么样的呢？

3.定义基础状态

根据dp的定义，很容易知道dp[0,0],dp[1,1]…dp[n,n]即只有一个堆的时候，只有先手可以拿到石头，后手拿的石头数量是0。然后根据状态转移规则，可以发现每个需要计算的值，就是以表格左边和下边的值来计算，每次以对角线的方向遍历，直到算出第dp[0,n]的值。
现在程序的任务很简单，从第一条对角线开始，依次遍历下一条对角线，直到填满最后一个格子。
以题目中求[5,3,4,5]为例：

初始状态

(i,j)	0	1	2	3
0	(5,0)			(?,?)
1		(3,0)
2			(4,0)
3				(5,0)

第一轮迭代

(i,j)	0	1	2	3
0	(5,0)	(5,3)		(?,?)
1		(3,0)	(4,3)
2			(4,0)	(5,4)
3				(5,0)

第二轮迭代

(i,j)	0	1	2	3
0	(5,0)	(5,3)	(8,4)	(?,?)
1		(3,0)	(4,3)	(8,4)
2			(4,0)	(5,4)
3				(5,0)

第三轮迭代

(i,j)	0	1	2	3
0	(5,0)	(5,3)	(8,4)	(9,8)
1		(3,0)	(4,3)	(8,4)
2			(4,0)	(5,4)
3				(5,0)

可以看到最后结果，先手最多可以拿9个石头，后手最多可以拿8个，所以答案是True。

代码

def stoneGame(self, piles: List[int]) -> bool:
    n=len(piles)
    dp=[[(0,0) for __ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i]=(piles[i],0)
    for k in range(1,n):
        for i in range(n-k):
            j=i+k
            left=piles[i]+dp[i+1][j][1]
            right=piles[j]+dp[i][j-1][1]
            if left>right:
                dp[i][j]=(left,dp[i+1][j][0])
            else:
                dp[i][j]=(right,dp[i][j-1][0])
    return dp[0][-1][0]-dp[0][-1][1]>0

彩蛋

到这里还没有结束，上面的解法可以应对一般的博弈问题，然而对于本题而言，注意题目条件

偶数堆石子排成一行，每堆都有正整数颗石子 piles [i] 。

假如将偶数堆石子按1,2,3,4…n来编号，比如10堆石子就从1到10来编号，那么这10堆一定可以分成2组，编号是奇数的堆和编号是偶数的堆，而题目又说石子总数是奇数，那么这2组一定是某组的数量大于另一组，要么奇数组大于偶数组，要么偶数组大于奇数组。
根据游戏规则，对于先手而言，他一定可以拿全编号是奇数的堆，或者拿全编号是偶数的堆，所以这题的答案是