877 石子游戏

石子游戏

下午精神迷离中，一时没弄清这个题目的规则，读这个题目好几遍才读懂。

假设都发挥出最佳水平 看到这里，我意识到并不是每一步取两侧较大的一个数就可以，而是要在当前情况下，遍历出最佳情况。

我立刻联想到了暴力破解国际象棋的深蓝，得出以下初步结论：

1. 要获得最佳发挥，是个递归，由剩余最后一堆情况，得出剩余两堆的最优解法，得出剩余n堆的最优解法
2. 每一步都可以选择头或尾，所以时间复杂度是

头立刻大了，问题肯定不能暴力解，我想到了用与堆数(N)等长的线性表缓存每一步的最优解，但是想不出最后一堆到底是哪一堆。

其实这里已经上路了，只不过自己没有自信，没敢继续想下去。不知道最后一堆是哪一堆，那就把n堆中任意一堆都作为最后一堆缓存下来，这样空间占用是 NxN 。

看到答案后…

到上面那里，我已经放弃了，转手就点开评论区，第一个评论：

return true;

我懵了，再看下去，有人解释了：

这是一个智力问题，对于偶数数量的堆，从头到尾给每堆设置下标：

1. 先手者可以确定自己每一步都选择偶数下标的堆或者奇数下标的堆。
2. 又因为总数量为奇数，所以 sum(偶数下标的堆) ≠ sum(奇数下标的堆)
3. 算出Max(sum(偶数下标的堆), sum(奇数下标的堆))后，先手者选择一直选奇数/偶数下标的堆就一定可以赢。

看看动态规划的解法

看了官方题解后，我意识到自己开始的想法方向对了。

建立一个二维数组 distinct[n][n] ，数组下标为distinct(i, j) 为 石头堆序列剩下(i…j)时，当前选手能获得的最大优势石子数目。所以当 i==j 时，distinct(i, j) == piles(i)，而当i<j时，

代码如下：

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

优化

上面的代码几个细节值得关注，对于每个distinct[i][j]的计算：

1. 我们只用到了distinct[i+1][j] 和 distinct[i][j-1]
2. 由于是从i=length-2，即序列末尾倒序迭代计算，所以distinct[i+1]行是计算过的
3. 而distinct[i][j-1]正是上次计算的结果

所以可以将二维数组优化为一维数组dist[length]，每次计算都使用上一次的结果，且i的每次迭代，都覆盖重写了dist数组，并用于下一次计算。
空间优化过的代码如下：

public boolean stoneGame(int[] piles) {
    //总数是奇数的情况下，先手必能获胜
    int length = piles.length;
    int[] dist = new int[length];
    for (int i = 0; i < length; i++) {
        dist[i] = piles[i];
    }
    for (int i = length - 2; i >= 0; i--)
        for (int j = i + 1; j < length; j++)
            dist[j] = Math.max(piles[i] - dist[j], piles[j] - dist[j - 1]);
    return dist[length - 1] > 0;
}

如果直接看优化过的代码，dist[j] 和 dist[j-1] 的含义很难弄懂。不过可以对照原始代码，可知

• dist[j] = ``distinct[i+1][j]
• dist[j-1] = distinct[i][j-1]