LeetCode486.预测赢家（递归+动态规划+博弈）

LeetCode486.预测赢家（递归+动态规划+博弈）

题目传送门

题目解析

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。 如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

两个玩家轮流从一个数组中取数字，每次只能取两端的数字，如果先手取得的数字总和大于等于后手，则返回true，否则返回false，每个玩家的玩法都是最优的。

递归

这里我们采用净胜分来判断，如果是玩家1得分，则净胜分加上得分，如果是玩家2得分，则净胜分减去得分，最终如果净胜分大于等于0，则玩家1获胜。 我们用一个solve(vectornums,int start,int end)函数来求当前玩家的最大得分，当前玩家有两种选择： 一、选择首部的数字，此时他的最大得分为：nums[start]-solve(vectornums,start+1,end) 其中solve(vectornums,start+1,end)为下一个玩家的得分，当前玩家的净胜分应该减去下一个玩家的得分。 二、选择尾部的数字，此时他的最大得分为：nums[end]-solve(vectornums,start,end-1) 得到当前玩家的两种可能得分后，取最大值即可。 代码

class Solution
{
public:
    bool PredictTheWinner(vector &nums)
    {
        return solve(nums, 0, nums.size()-1) >= 0;
    }
    int solve(vector &nums, int start, int end)
    {
        if (start == end)
        {
            return  nums[start];
        }
            int stasco = nums[start] - solve(nums, start + 1, end);
            int endsco = nums[end] - solve(nums, start, end - 1);
            return max(stasco, endsco);      
    }
};

动态规划

首先我们假设dp[i][j]为nums[i]到nums[j]中玩家的最大得分 通过上面递归的解法我们可以得到状态转移方程为：dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]) 当i>j时：dp[i][j]无意义 当i=j时：dp[i][j]=nums[i] 当i