企业产品网站模板,焦作网站建设哪家正规,建设街小学网站,网站的备案可以管几年文章目录1. 题目2. 解题1. 题目
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数#xff0c;随后玩家 2 继续从剩余数组任意一端拿取分数#xff0c;然后玩家 1 拿#xff0c;…… 。 每次一个玩家只能拿取一个分数#xff0c;分数被拿取之后不再可取…
文章目录1. 题目2. 解题1. 题目
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数随后玩家 2 继续从剩余数组任意一端拿取分数然后玩家 1 拿…… 。 每次一个玩家只能拿取一个分数分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。 最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组预测玩家1是否会成为赢家。 你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1
输入[1, 5, 2]
输出False
解释一开始玩家1可以从1和2中进行选择。
如果他选择 2或者 1 那么玩家 2 可以从 1或者 2 和 5 中进行选择。
如果玩家 2 选择了 5 那么玩家 1 则只剩下 1或者 2 可选。
所以玩家 1 的最终分数为 1 2 3而玩家 2 为 5 。
因此玩家 1 永远不会成为赢家返回 False 。示例 2
输入[1, 5, 233, 7]
输出True
解释玩家 1 一开始选择 1 。
然后玩家 2 必须从 5 和 7 中进行选择。
无论玩家 2 选择了哪个玩家 1 都可以选择 233 。最终玩家 1234 分比玩家 212 分获得更多的分数所以返回 True表示玩家 1 可以成为赢家。提示
1 给定的数组长度 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等那么玩家 1 仍为赢家。来源力扣LeetCode 链接https://leetcode-cn.com/problems/predict-the-winner 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 464. 我能赢吗状态压缩记忆化递归 / 博弈 LeetCode 877. 石子游戏DP LeetCode 1140. 石子游戏 IIDP* LeetCode 1406. 石子游戏 IIIDP LeetCode 1563. 石子游戏 VDP LeetCode 5447. 石子游戏 IV hard博弈DP LeetCode 1025. 除数博弈动态规划 LeetCode 5611. 石子游戏 VI贪心 LeetCode 5627. 石子游戏 VII博弈DP 天池 在线编程 双向取数博弈DP
dp[i][j] 表示剩余石子区间为 [i,j] 时当前玩家与另一个玩家的最大分差
class Solution {
public:bool PredictTheWinner(vectorint nums) {int n nums.size(), i, j;vectorvectorint dp(n, vectorint(n, INT_MIN));for(i 0; i n; i)dp[i][i] nums[i];for(int len 1; len n; len){for(i 0; ilen n; i){dp[i][ilen] max(nums[i]-dp[i1][ilen], nums[ilen]-dp[i][ilen-1]);// 当前选手 拿左边减去下一个选手的分差 拿右边减去下一个选手的分差}}return dp[0][n-1] 0;// 当前选手先手分差多或者等于win}
};4 ms 8 MB
状态空间只与上一行有关可以压缩代码略。 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
