Skip to content

Commit f4bc1ca

Browse files
authored
Merge pull request MisterBooo#29 from XiangSshou/patch-1
添加877.石子游戏数学分析部分的新思路
2 parents 3df06e5 + c52a2b8 commit f4bc1ca

File tree

1 file changed

+9
-1
lines changed

1 file changed

+9
-1
lines changed

notes/LeetCode第877号问题:石子游戏.md

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -111,6 +111,14 @@ class Solution {
111111
}
112112
```
113113

114+
下面给给大家介绍一种简单的策略作为参考,使用这种策略可以保证先取石头的喜羊羊一定能够获胜。
115+
116+
首先分别计算出序号为奇数和序号为偶数的石头堆中的石头总数,然后进行比较,如果奇数堆石头总数更多则喜羊羊永远保证自己选取奇数石堆,反之则选择偶数。
117+
118+
举例来说,假设石堆为 [ 5,10000,2,3 ] ,那么奇数石堆总和为 7(从 1 开始编号),偶数石堆总数为 1003 ,则喜羊羊要保证自己永远选择偶数堆即第四堆和第二堆,就可以取胜。
119+
120+
但是这种选择方法得到的**结果未必是最优解**,例如石堆为 [ 2,1,3,5 ] 当使用动态规划确保喜羊羊和灰太狼都选择最优解的时候,喜羊羊会拿走 [ 2,5 ] 两堆棋子,而灰太狼则拿走 [ 1,3 ] 两堆。但是使用这种策略在即使不是最优解的情况下依然可以保证喜羊羊胜利,所以作为先手的喜羊羊必定有方法取得比赛的胜利。
121+
114122
看完之后,你的心情是怎么样的?
115123

116124
此题的LeetCode 的评论区里一片吐槽:**这是什么沙雕题目!**
@@ -123,4 +131,4 @@ class Solution {
123131

124132

125133

126-
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)
134+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

0 commit comments

Comments
 (0)