预测赢家(博弈论，动态规划)

思路：动态规划：这里我们定义dp[i][j]为[i,j]中玩家1比玩家2最多能获得的分数.
首先直观可知dp[i][i]=nums[i].
[i,j]区间内玩家有两种操作方式：
1.先拿nums[j]，玩家1获得了nums[j].此时dp[i][j-1]就是玩家2比玩家1最多能获得的分数,此时玩家1比玩家2最多能获得的分数就是nums[j]-dp[i][j-1]
2.先拿nums[i]，玩家1获得了nums[i].此时dp[i+1][j]就是玩家2比玩家1最多能获得的分数,此时玩家1比玩家2最多能获得的分数就是nums[i]-dp[i+1][j]
所以：dp[i][j]=max(nums[j]-dp[i][j-1],nums[i]-dp[i+1][j])
判断dp[0][-1]与0的大小就可知玩家1是否获胜。

代码

class Solution { public: bool PredictTheWinner(vector& nums) { int n=nums.size(); int dp[n+2][n+2]; memset(dp,0,sizeof(dp)); int sum=0; for(int i=0;i if(j==i) dp[i][j]=nums[i]; else dp[i][j]=-1e9; } } for(int len=2;len int j=i+len-1; dp[i][j]=max(dp[i][j],max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])); } } return dp[0][n-1]>=0; } };

DFS版本

class Solution { public: bool Find(vector& nums,int ans1,int ans2,int l,int r,bool k) { if(l>r) { if(ans1>ans2) return true; else if(ans1==ans2) { if(k) return false; else return true; } else return false; } bool vis1=Find(nums,ans2,ans1+nums[l],l+1,r,k^1); if(!vis1) return true; bool vis2=Find(nums,ans2,ans1+nums[r],l,r-1,k^1); if(!vis2) return true; return false; } bool PredictTheWinner(vector& nums) { int r=nums.size()-1; return Find(nums,0,0,0,r,0); } };

本文来源：https://www.thyysj.com/info/267596.html

标签组：[动态规划] [dp]