题目分析

本题是一个博弈的题目，之前也给小伙伴们介绍过许多有关博弈的题型，博弈的题目有两类经典的解法，一个是动态规划，一个是数学方法，其中动态规划的思想类似于记忆化深度优先搜索。小伙伴能否根据这个提示写出正确的代码呢？

记忆化

第一眼我就想到了使用DFS进行求解，每次拿出一个数进行模拟，递归出口是只存在一个元素。但是要注意的是普通的DFS会产生TLE错误，因为本题可以从最前端或者最后端取出元素，所以每个元素有两种取法。本题的数组长度可以达到500，会超出时间限制。其中包括了很多的重复计算。如先取最右边，再取最左边和先取最左边再取最右边的结果是完全相同的。此时可以利用记忆化的思想，只需要遍历最左端和最右端两个端点即可。

**令子问题表示为亚历克斯从left到right可以获得的石子数量之和f(left, right)，假如亚历克斯拿了最左边的石子，那么李会从left + 1到right获得石子总数为f(left + 1, right)。亚历克斯获得石子的个数为sum(left, right) - f(left + 1, right)。同理，当亚历克斯拿了最右边啊的石子，那么亚历克斯获得的石子的个数为sum(left, right) - f(left, right - 1)。因此亚历克斯获得的石子数量之和最大值为sum(left, right) - max(f(left + 1, right), f(left, right - 1))**。

算法的时间复杂度为$O(n^2)$，空间复杂度为$O(n^2)$

下面是Java语言的题解

class Solution {
    public boolean stoneGame(int[] piles) {
        int[][] dic = new int[piles.length][piles.length];
        int sums = 0;
        for (int x : piles) { sums += x; }
        return 2 * find(0, piles.length - 1, sums, dic, piles) > sums;
    }

    private int find(int left, int right, int sums, int[][] dic, int[] piles) {
        if (left == right) { return piles[left]; }
        if (dic[left][right] == 0) {
            dic[left][right] = sums - Math.min(find(left + 1, right, sums - piles[left], dic, piles), find(left, right - 1, sums - piles[right], dic, piles));
        }
        return dic[left][right];
    }
}

下面是Kotlin语言的题解

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        val dic = mutableMapOf<Pair<Int, Int>, Int>()
        val sums = piles.sum()
        return 2 * find(0, piles.size - 1, dic, sums, piles) > sums
    }

    private fun find(left:Int, right:Int, dic:MutableMap<Pair<Int, Int>, Int>, sums:Int, piles:IntArray):Int {
        if (left == right) { return piles[left] }
        val pair = Pair<Int, Int>(left, right)
        if (!dic.contains(pair)) {
            dic[pair] = sums - Math.min(find(left + 1, right, dic, sums - piles[left], piles), find(left, right - 1, dic, sums - piles[right], piles))
        }
        return dic[pair]!!
    }
}

刷题总结

在前面也说过，动态规划类似于记忆化，本题也可以使用动态规划进行求解，只不过dp[i][j]要使用到dp[i][j - 1]和dp[i + 1][j]的状态，不能使用常规的遍历方法。本题还有一种更精妙的解法，可以直接return true，先手选择一定胜利，因为不是通用的解法，这里不做过多介绍，感兴趣的小伙伴们可以去看官方题解或其他博主的题解。