[LeetCode]Stone Game

首先dfs minmax tree肯定是可以解的，因为对手每一步都是最优的，所以我们每次考虑取左边还是取右边能让我们取更多的石头。时间复杂度O(2^N)，N为输入数组的长度，时间复杂度太高会TLE，代码如下：



优化的话很自然地会考虑DP，如果我们用dp[i][j]表示先手情况下，输入数组还剩从i到j的时候，我们能取的最大值。那么dp方程为dp[i][j] = max(sum[i][j] - dp[i + 1][j], sum[i][j] - dp[i][j - 1])，sum[i][j]代表i到j的区间和。这代表我们每次会选择给我们带来更多石头的一边。最后我们check dp[0][N - 1] > sum[0][N - 1] - dp[0][N - 1]即可。时间复杂度空间复杂度均为O(N^2)，代码如下：


空间复杂度可以进一步优化到O(N)，代码如下：



最后其实这道题有一个trick，先手的情况下，永远可以取所有奇数为或者偶数位的pile，我们只需要永远取较大的那一组即可，具体参考这篇文章。