原题地址（中等）

参考资料：力扣官方题解 力扣题解之零和博弈！记忆化 0ms 搞定 ~

方法1—递归

思路

注意：无论是哪位选手，所做的当前选择，一定是对自己来说最优，对对手来说最劣的选择。
**
本题是经典的零和博弈，两人的总得分不会有变化，永远都是 sum(nums) ，所以一方分数增加，必然会导致另一方的分数减少。

零和博弈（zero-sum game），又称零和游戏，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。它是指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”，双方不存在合作的可能。————《百度百科》


接下来我们用递归的思路来解这道题。

为了方便起见，我们定义 分数 的含义为： 玩家1的总分 - 玩家2的总分 ，即两者得分之差。

所以玩家1每次的选择就是使分数最大，而玩家2每次的选择就是使分数最小！**

由于每次的选择都有两个（左边或者右边），所以每次都会产生两种情况，对玩家1来说，这两种情况中分数大的那一种情况是最优的选择；对玩家2来说，这两种情况中分数小的那一种情况是最优的选择。

最后，分数如果>=0，则玩家1获胜，否则玩家2获胜。

代码

我们定义 turn 来区分当前玩家是哪一个， turn=1 表示当前是一号玩家， turn=-1 表示二号玩家；
total() 函数返回值为分数，即玩家1总分 - 玩家2总分;

  1. class Solution {
  2. public:
  3.     bool PredictTheWinner(vector<int>& nums) {
  4.         return total(nums, 0, nums.size() - 1, 1) >= 0;
  5.     }
  7.     int total(vector<int>& nums, int start, int end, int turn) {
  8.         if (start == end) {
  9.             return nums[start] * turn;
  10.         }
  11.         // 每次都有两种选择
  12.         int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
  13.         int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
  14.         // 玩家1目的：使分数尽可能大；   玩家2目的：使分数尽可能小
  15.         if(turn==1)     return max(scoreStart, scoreEnd);
  16.         else    return min(scoreStart, scoreEnd);
  17.     }
  18. };

时空复杂度

每次都有两种选择，所以时间复杂度为 O(2^N)；空间复杂度取决于递归使用的栈空间，同一时间栈的深度最大为 N ，所以空间复杂度为 O(N)

未经任何优化的递归可真慢。。。
image.png

方法2—记忆化递归

记忆化递归听着挺高级的，其实就是把递归过程中一些重复计算的东西拿空间记录下来，防止重复计算，也就是拿空间换时间。
嗯，确实是比递归更高级的做法emmm

方法1中存在大量的重复劳动，以致耗时很长，比如说 nums=[1,2,3,4,5] ，现在玩家1选择了 1 ，玩家2选择了 5 ，那么还剩下子问题为 [2,3,4] 。如果现在玩家2选择了 1 ，玩家1选择了 5 ，那么剩下的子问题还是 [2,3, 4] ，这就造成了重复计算。

我们定义一个记忆数组 memory ，memory[start][end] 表示 [start, end] 这个区间的问题的答案，也就是方法1中 total(nums, start, end, turn) 的返回值，也就是从 start 到 end 这个子问题的解，我真的好啰嗦。
~~

代码

对方法1的代码稍作修改可得。

  1. class Solution {
  2. public:
  3.     bool PredictTheWinner(vector<int>& nums) {
  4.         int memory[21][21] = {0};  // 记忆数组
  5.         return total(memory, nums, 0, nums.size() - 1, 1) >= 0;
  6.     }
  8.     int total(int memory[21][21], vector<int>& nums, int start, int end, int turn) {
  9.         if (start == end)   return memory[start][end] = nums[start] * turn;
  10.         if (memory[start][end] != 0)    return memory[start][end];
  11.         int scoreStart = nums[start] * turn + total(memory, nums, start + 1, end, -turn);
  12.         int scoreEnd = nums[end] * turn + total(memory, nums, start, end - 1, -turn);
  13.         if(turn==1)     return memory[start][end] = max(scoreStart, scoreEnd);  
  14.         else    return memory[start][end] = min(scoreStart, scoreEnd);
  15.     }
  16. };

时空复杂度

时间复杂度量级没有变，但是耗时确实减少了，因为少了计算的过程。空间复杂度增长为 O(L^2) ，在本题中 L=21

直接超过100%你敢信。。。
image.png

方法3—动态规划

由方法2，很自然地就可以过渡到动态规划算法。