零和博弈

概念介绍

零和博弈就是字面意思所表示的博弈情形，博弈双方在博弈过程中的总价值是不变的，双方某一方价值的增长必然会导致另一方价值的缩减，零和博弈是具有先手优势和后手劣势的。

1. 先手优势
   所谓先手优势其实指的是博弈双方具有优先选择权的一方，具有优先选择的优势，他可以优先控制选择的走向。
2. 后手劣势
   后手劣势指的是博弈双方中，后手一方在选择时会受到先手优势的影响，尽管博弈双方都可以选择最有利于自己的顺序进行，但是后手是在先手制约下的最优选择，所以后手是博弈双方中具有劣势的一方。

总之零和博弈作为一种常见的博弈方式我们只需要记住两个重要点——①博弈总和不变；②博弈双方在自己的立场上都是选择最优的。

算法实例

来源：力扣（LeetCode）
链接：预测赢家
题目描述如下：
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

1. 按照博弈双方总是在自己的立场选择最优的解，那么意味着假如当前数组的左右两端序号分别为left和right，那么当前长度下当前做出选择的一方应当做出最有利于自己的选择，也即价值最大的选择。现在当前选择的一方可以选择的方案有拿left或者拿right两种选择，他选择其中一方的依据是使得自己的利益最大，问题是如何判断拿取left或者right后的利益呢？我们知道的是当前选择方选择left或者right中一个后，后一方在剩余的数组中选择也是最有利于他的，所以假如另外一方在之后的选择中选择了一个最优方案，该方案的最大利益我们也已经知晓了为S，那么我们该如何得到当前一方最大利益呢？
2. 这就需要用到第二个重要点，零和博弈中博弈的总价值是不变的，所以当我们知道剩余数组中另一方的最优价值为S，那么当前选择方所获得的价值也就确定了——即剩余数组价值总和-S；但是由于当前方需要选择价值最大的策略，所以他需要在选择left或者right中做一个权衡，所以当前选择方的最大利益为max（选择left的利益+去掉left后的剩余数组价值总和-去掉left后另一方的最优选择，选择right的利益+去掉right后的剩余数组价值总和-去掉right后另一方的最优选择）；

通过上面分析我们实际上已经可以得到算法实现了，按照这个思路主要有两种实现方式：

1. 递归实现

class Solution { 
    public: int sum(vector<int>& nums,int left,int right){ 
    int a=0; for(int i=left;i<=right;i++){ 
    a=a+nums[i]; } return a; } int DFS(vector<int> &nums,int left,int right){ 
    if(left==right){ 
    return nums[left]; } return max(nums[left]+sum(nums,left+1,right)-DFS(nums,left+1,right),nums[right]+sum(nums,left,right-1)-DFS(nums,left,right-1)); } bool PredictTheWinner(vector<int>& nums) { 
    int player1=DFS(nums,0,nums.size()-1); int player2=sum(nums,0,nums.size()-1)-player1; return player1>=player2?true:false; } }; 

时间空间复杂度：

2. 动态规划

class Solution { 
    public: int sum(vector<int>& nums,int left,int right){ 
    int a=0; for(int i=left;i<=right;i++){ 
    a=a+nums[i]; } return a; } bool PredictTheWinner(vector<int>& nums) { 
    vector<int> A(21,0); vector<vector<int> > dp(21,A); for(int i=0;i<nums.size();i++){ 
    for(int j=0;j+i<nums.size();j++){ 
    if(i==0){ 
    dp[j][j+i]=nums[j]; continue; } dp[j][j+i]=max(nums[j]+sum(nums,j+1,j+i)-dp[j+1][j+i],nums[j+i]+sum(nums,j,j+i-1)-dp[j][j+i-1]); } } int player1=dp[0][nums.size()-1]; int player2=sum(nums,0,nums.size()-1)-player1; return player1>=player2?true:false; } }; 

时间空间复杂度：

3. 记忆化搜索

class Solution { 
    public: //dp数组，用以记录最优子结构的值，避免重复操作 vector<int> A=vector<int> (21,0); vector<vector<int> > dp=vector<vector<int> > (21,A); int sum(vector<int>& nums,int left,int right){ 
    int a=0; for(int i=left;i<=right;i++){ 
    a=a+nums[i]; } return a; } int DFS(vector<int> &nums,int left,int right){ 
    //该算法其实是记忆化搜索的过程，因此dp的顺序是深度优先遍历的顺序。 if(left==right){ 
    //如果left==right，此时直接返回最优值 dp[left][right]=nums[left]; return dp[left][right]; } //如果之前[left+1,right]区间的值已经DFS求出了，那么直接使用即可，这就是记忆化搜索的过程， //之前已经搜索过的子结构，可以直接使用其值，避免重复操作，可以有效的降低复杂度。 if(dp[left+1][right]!=0){ 
    if(dp[left][right-1]!=0){ 
    dp[left][right]=max(nums[left]+sum(nums,left+1,right)-dp[left+1][right],nums[right]+sum(nums,left,right-1)-dp[left][right-1]); }else{ 
    dp[left][right]=max(nums[left]+sum(nums,left+1,right)-dp[left+1][right],nums[right]+sum(nums,left,right-1)-DFS(nums,left,right-1)); } }else if(dp[left][right-1]!=0){ 
    dp[left][right]=max(nums[left]+sum(nums,left+1,right)-DFS(nums,left+1,right),nums[right]+sum(nums,left,right-1)-dp[left][right-1]); }else{ 
    dp[left][right]=max(nums[left]+sum(nums,left+1,right)-DFS(nums,left+1,right),nums[right]+sum(nums,left,right-1)-DFS(nums,left,right-1)); } return dp[left][right]; } bool PredictTheWinner(vector<int>& nums) { 
    int player1=DFS(nums,0,nums.size()-1); int player2=sum(nums,0,nums.size()-1)-player1; return player1>=player2?true:false; } }; 

时间空间复杂度：

结果分析

从上面的例子可以看出各种方案的时间复杂度和空间复杂度差距，记忆化搜索通俗的讲就是搜索+动态规划。而搜索方式一般有深度优先搜索和宽度优先搜索这两种，本例子中采用的是深度优先搜索的方式。记忆化搜索其实就是一个定序的过程，因为动态规划过程中需要利用子问题的解推出更大的父问题的解，而这是一个自底向上的过程，但是很多问题中我们可能很难确定求解子问题的顺序，也就是确定一个合理的拓扑顺序，使得将要推导的子问题需要的所有子问题的解都在其之前已经求解出来了。记忆化搜索其实就是一个自顶向下的过程，它是从根节点开始搜索，如果遇到了需要求解的子问题，会先查看是否已经有该子问题计算的记录，如果有的话就直接使用，否在还会继续按照搜索的顺序求解各个子问题的解，最终得到该子问题的解。遍历结束后遍历序列（也即得到的遍历树，本例中为深度优先搜索树）就是动态规划推导各个子问题的顺序，根节点的结果也就是最终结果。

总之来说，记忆化搜索其实就是利用搜索的过程确定一个动态规划求解子问题的拓扑序列，使得动态规划能够顺利推导，而动态规划则是利用我们已知的一些显而易见的拓扑序列进行求解。