leetcode_486. Predict the Winner
2024-08-27 00:28:14
https://leetcode.com/problems/predict-the-winner/
题目描述：给定一个非负的积分数组，玩家1可以从数组两端任取一个积分，接着玩家2执行同样的操作，直至积分被取尽，总分大的获胜。两人都以最优决策进行游戏。对每个数组输出玩家1是否能获胜。
解法1：
使用递归，两者依次取数。
class Solution{
public:bool PredictTheWinner(vector<int>& nums){return dfs(nums, , nums.size()-, , , );
}
bool dfs(vector<int>& nums, int st, int en, int p1, int p2, bool role){
if(st == en){
if(!role && p1+nums[st]>=p2)
return true;
else if(role && p1<p2+nums[st])
return true;
else
return false;
}
if(!role){
bool c1 = dfs(nums, st+,en,p1+nums[st],p2,!role);
bool c2 = dfs(nums, st,en-,p1+nums[en],p2,!role);
if(c1 && c2) //若从任意一端取数后，对手都胜，那么当前玩家必败
return false;
else
return true;
}else{
bool c1 = dfs(nums, st+,en,p1,p2+nums[st],!role);
bool c2 = dfs(nums, st,en-,p1,p2+nums[en],!role);
if(c1 && c2)
return false;
else
return true;
}
}
};
解法二：官方题解
对于两个玩家而言，玩家1的总分s1，玩家2的总分s2，dis=s1-s2，若玩家1胜，dis>=0，否则dis<0。依旧使用递归，双方依次取数，玩家1希望差值越大越好，玩家2希望差值越小越好。
int dfs(vector<int>& nums, int st, int en, bool role)
函数返回值为：在nums[st,en]上由role取数后的总分差值dis。
class Solution{
public:bool PredictTheWinner(vector<int>& nums){return dfs(nums, , nums.size()-, )>=;
}
int dfs(vector<int>& nums, int st, int en, bool role){
if(st == en){
if(role == )
return nums[st];
else
return -nums[st];
}
if(!role)
return max(nums[st] + dfs(nums, st+, en, !role), nums[en]+dfs(nums, st, en-, !role));
else
return min(-nums[st] + dfs(nums, st+, en, !role), -nums[en]+dfs(nums, st, en-, !role));
}
};
解法三：官方题解，动态规划
dp[st][en]：玩家1在nums[st,en]上取数过后的差值dis(dis=s1-s2)
在nums[st][en]上的dis: dp[st][en]取决于{num[st], dp[st+1][en]}和{num[en], dp[st][en-1]}，即仅取决于nums[st][en]子数组上的dp和num[st],num[en]。
class Solution{
public:
bool PredictTheWinner(vector<int>& nums){
int dp[][];
memset(dp,,sizeof(dp));
for(int tail=; tail<nums.size(); tail++)
for(int head=tail; head>=; head--){
int get_head = nums[head] - dp[head+][tail];
int get_tail = nums[tail] - dp[head][tail-];
dp[head][tail] = max(get_head, get_tail);
}
return dp[][nums.size()-]>=;
}
};
最新文章
- AppCan学习笔记----关闭页面listview动态加载数据
- Python文件操作题
- Ajax 无刷新上传文件插件 uploadify 的使用
- AngularJS-入门篇
- JavaScript Table行定位效果
- (转) Reinforcement Learning for Profit
- UVA 10254 - The Priest Mathematician (dp | 汉诺塔 | 找规律 | 大数)
- ftk学习记（icon篇）
- C#基础（二）拆箱与装箱，循环与选择结构，枚举
- 洛谷P2664 树上游戏(点分治)
- Python Learning: 03
- 浅谈flex布局中小技巧
- js之history
- Salesforce Lightning Builder Flows (Salesforce Lightning 构建Flows)
- Visual Studio UML类图
- Xcode工程编译错误之iOS开发之Sending '__strong typeof (xxx)' (aka 'xxxx *__strong') to parameter of incompatible type 'id<xxx>'
- LeetCode - Unique Email Addresses
- Spring事务管理的配置
- php操作mysql几个常用操作
- Feign 请求拦截器和日志