Leetcode 877 StoneGame

解题方案1：

1. 整理一下规则：
   Alex、Lee两个人，Alex先手，Lee后手。
   每次只能拿 第一堆 或者 最后一堆
   两个人拿取的策略 都是最优的 都为了打败对方

2. 方程：
   设 i 为第一堆石子下标，j 为最后一堆石子下标
   如果 先手 选择 i，则后手只能选择 i+1 或者 j
   如果 先手 选择 j，则后手只能选择 i 或者 j-1

   则先手与后手石子堆的差为：
   piles[i] - opt(piles, i+1, j) 或者 piles[j] - opt(piles, i, j-1)
   opt(piles, i, j) 的意思是从piles数组里下标 i 到 j 中选
   取石子堆的最佳组合。
   因为中间选择过程我们不清楚，所以可以用递归去穷举。

   最终结果只要大于0我们就认为先手胜了

   代码如下：

i = 0
j = len(piles)

def opt(piles, i, j):
   if i==j:
       return piles[i]
   if j>i:
       return max( piles[i] - opt(piles, i+1, j),
                           piles[j] - opt(piles, i, j-1) )

return opt(piles, i, j) > 0

解题方案2：

能用递归的基本都能用递推去解决，递推的过程也就是动态规划。笔者是这么理解的，不一定正确，因为本人觉得递推和动态规划都是递归的一个逆过程，递归是 从问题最终出发，而递推和动态规划都是 从问题的开始出发。

具体怎么想到解题的思路，其实我也不知道。可能题做多了就能知道吧，我也是看了别人的答案想了很久才想明白。

解题思路，方案一讲讲述过的就不再累述了

1. 既然是从 问题的开始出发，那就从游戏开始的第一步来， 这里的 游戏开始 准确的来说应该是从递归的最后一步开始。一开始还是很难理解的，多想想就能明白之中的奇妙了。
   2.方案一递归到底的时候只有一个石子堆，即i=j的情况，然后会不断上升到两个石子堆，三个石子堆取最佳博弈的情况，拿leetcode第一个例子[5,3,4,5]来说的话：
   递归是考虑了只剩下单独石子堆的情况： [5] [3] [4] [5]
   剩下两个石子堆的情况：[5,3] [3,4] [4,5]
   剩下三个石子堆的情况：[5,3,4] [3,4,5]
   最后全集的情况：[5,3,4,5]
   我们需要做的就是 自底而上的把最佳博弈情况求出来 因为单独石子堆的情况最佳博弈情况 是 两个石子堆里求出最佳博弈情况的基础，以此类推。
2. 最佳博弈情况方程 （状态方程）：
   与递归的方程是一样的：
   max( piles[i] - opt(), piles[j] - opt() )
   求 先手 在当前状态下的选择的石子堆减去 之前两者博弈的石子差（这个过程是累计的来得，即我们要每次记住当前人选择的石子与后者选择的石子差）。
   举个例子：
   因为递归最后一步是后手选择，转为递推和动态规划的话，后手是第一步。
   设A为 先手， B为 后手
   [5,3,4,5]
   假设A选择了第一个5，则B可以选择3或者5，为了得到最佳博弈，B会选择5，此时的opt就为5。因为A选择了5，此时的opt就是5-5=0。
   接下来A肯定选择4， 则B就只能选择3了，B选择后的最佳博弈结果是3-0=3，A选择后的最佳博弈结果就是4-3=1。
   这里是需要好好理解一下的。
   3.因为最佳博弈结果是要被记录下来然后被后者使用的，就是为了避免递归过程中重复计算一样的子过程。
   考虑到有两个变量选最左边i还是选最右边j，这里就构建二维数组opt[N][N]来记录了。N为piles数组的长度。
   opt[i][j]是用来记录所有子问题的最佳博弈结果，因此就有在方案2上面说的所有情况。这就是用二维数组记录的原因。
   opt[1][3]表示piles[1]到piles[3]中的最佳博弈结果。
   从单个情况opt[N][N]开始推到全集opt[0][N], 然后这个opt[0][N]就是我们需要求得的最后结果。

代码如下:
上面谈到的opt改成了dp

dp = [ [0 for _ in range (0,length)] for _ in range (0,length)]

for i in range (0,length):
    dp[i][i] = piles[i]
    
for i in range (length-2,-1,-1):

    for j in range (i+1,length):

        dp[i][j] = max( piles[i] - dp[i+1][j], piles[j] - dp[i][j-1] )

return dp[length-1][length-1] > 0