[LeetCode]Predict the Winner

递归的做法就是minimax，每次递归我们就两种可能，我们要计算的就是当前player取的所有数的和对手optimal move情况下取的和的差值。如果第一个层对应的值为正就说明可以赢，否则就输。时间复杂度O(2^N)，N为array的长度。代码如下：


另一个思路就是dp，dp[i][j]代表当前player在还剩从i到j的元素的时候，能比对手多取的值。那么我们有递推公式:

• dp[i][j] = max(array[i] - dp[i + 1][j], array[j] - dp[i][j - 1])

时间空间复杂度均为O(N^2)，代码如下：