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

发布时间:2021-02-12 发表于话题:预测赢家软件收费嘛 点击:13 当前位置:财神股票资讯网 > 游戏 > 预测赢家(博弈论,动态规划) 手机阅读

思路:动态规划:这里我们定义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

相关APP下载

热门话题

游戏推荐文章

游戏热门文章