关于博弈

你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。

石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。比如有三堆石头 piles = [1, 100, 3]，先手不管拿 1 还是 3，能够决定胜负的 100 都会被后手拿走，后手会获胜。

假设两人都很聪明，请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。比如上面那个例子，先手能获得 4 分，后手会获得 100 分，你的算法应该返回 -96。

为什么说博弈可以用动态规划解决呢？主要原因是因为博弈中的每一步，都是受到前一步操作影响的。这其中就涉及到了状态转移。

思路分析

面对一堆石头，只能从左右两边进行选择，因为两人都聪明，那么说明每次他们的选择，都一定会选择能让自己分数最大的。
所以这里就是第一个重点：每次选择，要让自己的石头数量最大。
只能从左边或者右边选择，那么只需要比较这两边的哪个能让自己分高一些就行了。

第二：先手的选择，会对后手也造成影响。我觉得这一点是本题目最麻烦的最难理解的地方。

假如现在数量的数组是piles现在是对[left..right]这几堆石头进行选择。

我作为先手:
那么我会比较选择piles[left]和piles[right]哪个能让我得到的分最大,这里并不只能单纯比较piles[left]和piles[right]哪个大，因为你受上一步影响。并且你也不能每次都选择最大的，因为你还有一个聪明的对手存在。
如果是选左边：即选择piles[left]，然后我们两对[left+1...right]继续博弈，而在面对[left+1...right]中，我肯定是作为后手。
如果是选右边，即piles[right]，然后我们两对[left...right-1]继续博弈，而在面对[left...right-1]中，我肯定是作为后手。

而我作为后手
如果对手选了piles[left]，那么剩下的是[left+1...right]，而我在对这剩下的部分的博弈中，将获得先手。
如果对手选择里piles[right]，那么剩下的是[left...right-1]，而我在对这部分的博弈中，也将获得先手。

状态转移

令对[i...j]堆石头的博弈的结果为res,而每个结果中有first和second，分别为先手后手。

从前面的分析可以很容易得知:
res[i...j].first=Max(piles[i]+res[i+1...j].second,piles[j]+res[i...j-1].second)
res[i...j].second=first is left?res[i+1...j].first : res[i...j-1].first

而当i=j的时候，即只有一堆石头，则此时first=piles[i]，second=0。因为只有一堆，肯定是被先手的人拿了。

所以，我们需要一个二维数组dp[][]，来记录从i->j这些堆石头，的先手得分和后手得分。
并且，我们更新这个数组的顺序也很重要，我们遍历到i,j的时候，得先保证i+1,j和i,j-1是已经更新过的，这算是细节上的一个小难点吧。建议不太熟悉的话，可以在草稿本上画一个3x3的矩阵，看看怎么保证遍历的顺序。

代码实现

  public int selectStone(int[] piles) {
        Result[][] dp = new Result[piles.length][piles.length];
        //i为左边,j为右边
        for (int j = 0; j < piles.length; j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    dp[i][j] = new Result(piles[i], 0);
                } else {
                    //本轮的先手
                    int f = Math.max(piles[i] + dp[i + 1][j].second, piles[j] + dp[i][j - 1].second);
                    //是否会选择左边
                    boolean isLeft = piles[i] + dp[i + 1][j].second > piles[j] + dp[i][j - 1].second;
                    int s;
                    if (isLeft) {
                        //本轮的后手,如果对方选了左边，那么我只剩[j+1..i]这部分，而在上一轮中我一定是作为先手。
                        //并且已经对[j+1..i]这部分做出了选择
                        s = dp[i + 1][j].first;
                    } else {
                        //右边同理
                        s = dp[i][j - 1].first;
                    }
		    //更新dp数组
                    dp[i][j] = new Result(f, s);
                }
            }
        }
        return dp[0][piles.length - 1].getDValue();
    }

    class Result {

        public Result(int first, int second) {
            this.first = first;
            this.second = second;
        }
	//获取先手和后手的差值
        public int getDValue() {
            return this.first - second;
        }

        public int first;

        public int second;
    }

我这里的遍历方式，是“勾型”遍历，大概是这个样子: