leetcode之石子游戏（博弈类动态规划）数据结构与算法HarryXu的博客-

• 这是一道博弈类的动态规划题目，题目假设两者都能发挥出最佳水平，那么这题如果用贪心算法（每次选取最左边和最右边的最大值）其实是不行的，比如[1,100,3];不管先手一开始拿的是最左边的1还是最右边的3，那么后手都能拿到100，后手就会赢。所以这里我们采用动态规划去解决。

思路如下：（毕竟是动态规划，那我们就按照动态规划的三步来走）

1. 首先就是定义状态dp[i][j],用来表示在i~j堆石子中，亚历克斯比李多拿的石子。一般来说动态规划，我们看看是不是很明显的二维动态数组，如果是的话我们先直接定义二维数组，然后到后面再去考虑状态压缩。
2. 这里的状态转移方程比较难找，我们可以这样思考：
   2.1 如果这里只有两堆石子[3,5]，我们怎么保证亚历克斯的dp[0][1]最优值？ 如果亚历克斯一开始拿走的是piles[0]=3，此时李变成了先手，那么状态是不是变成了要找李的dp[1][1],（亚历克斯的最优选取策略就变成了李的最优选取策略）即dp[i+1][j]表示对手比当前的选手多出来的石子数量，那么此时亚历克斯比李多的石子数量就是“piles[0] – dp[1][1]”；同理，如果亚历克斯一开始拿走的是piles[1]，那么此时李变成了先手，那么亚历克斯比李多的石子数量就是“piles[1] – dp[0][0]”，我们选取两者之间的最大值就好了。
   2.2 如果此时是三堆石子[3,5,1]，我们可以同样这样思考，如果亚历克斯一开始拿走的是piles[0]，那么是不是此时就该比较“piles[0] – dp[1][2]”；同理，如果亚历克斯一开始拿走的是piles[2]，那么此时李变成了先手，那么亚历克斯比李多的石子数量就是“piles[2] – dp[0][1]”。
   3.3 以此类推，到n堆石子的时候，我们判断max（piles[0] – dp[1][n-1]，piles[n-1] – dp[0][n-2]）即可；
3. 最后一步就是确定base case了，我们刚开始定义状态转移方程的时候，发现了如果只有i==j的时候，我么的dp[i][i]表示的就是亚历克斯比李多拿的石子，那么这个石子就是等于piles[i];所以我们的初始状态就是dp[i][i] = piles[i]。
4. 附上代码：

class Solution { public boolean stoneGame(int[] piles) { int n = piles.length; int[][] dp = new int[n][n]; for(int i=0;i<n;i++){             dp[i][i] = piles[i]; } for(int len=1;len<n;len++){ for(int i=0;i<n-len;i++){ int j = i + len;                 dp[i][j] = Math.max(piles[i] - dp[i+1][j],piles[j] - dp[i][j-1]); } } return dp[0][n-1] > 0; } } 

• 此时我们再来考虑状态压缩。我们发现在更新dp数组的时候，我们只是用到了对角线上的dp数组，而且我们更新的顺序是从左上角到右下角，并没有在更新一个dp元素的时候又更新了这个dp数组的左上角元素，所以我们可以使用一位数组来解决这个问题。

class Solution { public boolean stoneGame(int[] piles) { int n = piles.length; int[] dp = new int[n]; for(int i=0;i<n;i++){             dp[i] = piles[i]; } for(int len=1;len<n;len++){ for(int i=0;i<n-len;i++){ int j = i + len;                 dp[i] = Math.max(piles[i] - dp[i+1],piles[j] - dp[j-1]); } } return dp[n-1] > 0; } }