leetcode 第877题石子游戏 python解法（用时420ms）

最新推荐文章于 2022-04-04 21:51:22 发布

六月香樟

最新推荐文章于 2022-04-04 21:51:22 发布

阅读量766

点赞数 2

分类专栏： leetcode解题文章标签： leetcode 算法动态规划

本文链接：https://blog.csdn.net/Whyalwaysxu/article/details/85276646

版权

博客详细解析了LeetCode第877题的石子游戏问题，采用Python解决，用时420ms。通过动态规划和逻辑判断分析，解释了如何在双人博弈中保证先手优势。动态规划的状态转移方程是dp[i][j]=max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])，利用极小化极大算法。最后提供了一个简单的解决方案，直接返回True，表明先手总是能赢。" 77650478,5692819,一维与二维数据插值技术详解,"['数值计算', '数据处理', '数学方法', '编程算法']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

leetcode 第877题石子游戏 python解法（用时420ms）

该题是典型的双人回合制博弈游戏，两个人轮流从石子堆中拿出石子，其中石子都是按行一行行排好的，每个回合只能从头或者尾拿出一行石子。石子排列的行数是偶数，而且石子的总数是奇数，这样说明到最后不会出现平局。

问题分析

动态规划

这题本意是要求使用动态规划，动态规划最重要的是要写出状态转移方程。假设在某个状态时石子的排列为[2,4,7,1,8]，数组中的每个数表示该行石子的总数。按照题目要求只能在头或尾取石子，所以本回合能取的只有2或8，而到底取哪一个，这是要进行比较才能做出选择。由于双方都不是傻子，所以每个回合选手选取的数都是对自己最有利的，换句话说，是对对方最不利的。
所以，这里我们选取其中某一个选手的角度展开问题，首先该选手会选取一个数作为自己的点数，所以是正值，接下来是对手的回合，他也会选取一个数，那么我们要将第一个数减去这个数，如果是整数，说明第一位选手取得多（赢了），如果是负数说明比较少（输了）。所以状态转移方程是 dp[i][j]=max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) 。状态方程要使用max（）函数，这里涉及到另一个知识点即：极小化极大算法（Minimax，关于这部分大家可以上网查一查别的资料，很有趣）。前面说过，双方都不是傻子，所