思路

Leetcode 的 486 题：给定数组nums，玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0]或nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。玩家都会使用最优的取法，玩家 1 分数 >= 玩家 2 的的时候，返回true，否则返回false，换句话说，求先手是否能必胜。

以nums = [1,5,2]为例，记玩家 1 和 2 分数之差为 $ans$，枚举一下：

graph TB
A("[1,5,2] ans = 0") -->|Player 1 select 1|B("[5,2] ans = 1")
A-->|Player 1 select 2|C("[1,5] ans = 2")
B-->|Player 2 select 5|D("[2] ans = -4")-->|Player 1 select 2|E("[] ans = -2")
B-->|Player 2 select 2|F("[5] ans = -1")-->|Player 1 select 5|G("[] ans = 4")
C-->|Player 2 select 1|J("[5] ans = 1")-->|Player 1 select 5|K("[] ans = 6")
C-->|Player 2 select 5|M("[1] ans = -3")-->|Player 1 select 1|N("[] ans = -2")

很明显，这种情况下，先手不能必胜，即 $ans >= 0$。

感觉解这种博弈的题目，需要关注的是怎么利用递归模拟玩家的选择

递归

两个玩家在下标 $l$ 到 $r$ 之间的数组进行选择。先手是否必胜，我们只需关心玩家 1、2 分数之差是否 >=0。

这里一开始我写的时候，递归会把累计的分数之差也作为入参，这就给记忆化搜索和推导出递推式造成了麻烦…

在看了题解之后得到了以下思路：假如玩家 1 选择了下标 $l$，此时分数之差是 $l$ 位置的数字减去 $l + 1$ 到 $r$ 之间玩家 2 能得到的最大分数 $sl$。选择了 $r$ 同理，得分记为 $sr$，因此这一步玩家 1 的得分为 $\max(sl,sr)$。这样子这个问题被拆分为多个子问题，这里使用 DFS 的方法进行求解，每一步返回的是当前玩家所能获取的最大分数。

因为是玩家 1 先手，所以 DFS 返回的是玩家 1 - 玩家 2 的分数。

ts
function predictTheWinner(nums: number[]): boolean {
    const dfs = (l, r) => {
        if (l >= r) {
            return nums[l]
        } else {
            return Math.max(
                nums[l] - dfs(l + 1, r),
                nums[r] - dfs(l, r - 1)
            )
        }
    }
    return dfs(0, nums.length - 1) >= 0 
};

时间复杂度 $O(2^n)$，其中 $n$ 是数组的长度，空间复杂度 $O(n)$。

很显然会有重复的计算，所以加上缓存：

ts
function predictTheWinner(nums: number[]): boolean {
    const cache = [], len = nums.length
    const dfs = (l, r) => {
        const index = l * len + r
        if (cache[index] !== undefined) {
            return cache[index]
        }
        if (l >= r) {
            return cache[index] = nums[l]
        } else {
            return cache[index] = Math.max(
                nums[l] - dfs(l + 1, r),
                nums[r] - dfs(l, r - 1)
            )
        }
    }
    return dfs(0, nums.length - 1) >= 0 
};

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

递推

把记忆化搜索转为递推式动态规划，利用二维数组记录当前索引分别为 $l$、$r$ 时，当前玩家在这个区间获得的最大分数之差。

在这里画图好不方便，有空把外链导入的功能加上

以nums = [1,5,2]为例，很显然，当区间长度为 1 时，能获得的分数之差就是对应的数字，有：

有状态转移方程：

$$dp[i][j] = \max(nums[i]-dp[i + 1][j],nums[j]-dp[j - 1][i])$$

这里我们选择从右下角开始迭代，结果为dp[0][nums.length - 1]，也就是在整个nums数组上的最大分数差：

ts
function predictTheWinner(nums: number[]): boolean {
    const dp = [], len = nums.length
    for (let i = 0; i < len; i++) {
        dp[i] = []
        dp[i][i] = nums[i]
    }
    for (let i = len - 2; i >= 0; i--) {
        for (let j = i + 1; j < len; j++) {
            dp[i][j] = Math.max(nums[j] - dp[i][j - 1], nums[i] - dp[i + 1][j])
        }
    }
    return dp[0][len - 1] >= 0
};

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

然后，可以发现，每次迭代都只依赖dp[i + 1][j]、dp[j - 1][i]这两个 dp 中的元素，可以把二维的dp优化掉：

其实这里每一轮，操作列的时候，只依赖每一列的（从上到下数）第一个已知元素，计算出新的元素后，覆盖掉dp数组中原来的元素就好了。

ts
function predictTheWinner(nums: number[]): boolean {
    const dp = [...nums], len = nums.length
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i + 1; j < len; j++) {
            dp[j] = Math.max(nums[j] - dp[j - 1], nums[i] - dp[j])
        }
    }
    return dp[len - 1] >= 0
};

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。