day134-LeetCode 292. Nim Game

题目

(动态规划)
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

分析

动态规划的话。先逐步分析。先分析可能的情况。

剩下1-3个石头,我赢。
剩下4个石头,我先拿1-3个,输。
剩下5个石头,我先拿1个,然后剩下4个轮到他先,我赢。先拿2-3个的话,我输。
剩下6个石头,我先拿1个,回到上一步5个石头他先。我先拿两个,就是4个石头他先,他输。
剩下7个石头,我先拿1个,回到上一步6个石头他先拿,他拿两个的话就回到5个石头情况,他赢。 我拿3个才能到状态4个石头他先拿,他输。
所以,我得想办法让他面前的石头数量到4个石头,这样有5-7个石头时我先拿的话都可以赢。
如果是8个石头,我先拿至少一个,剩下5-6个石头他先拿,只要他让我面前剩下4个,他就有优势,我都会输。

4和8为倍数关系。归纳总结出初步结论,有可能是4的倍数的时候,我先拿就输。

题解

function canFirstWinNimGame (sum) {
if (sum < 4) { // 1-3的整数,先拿肯定赢
return true
}
return n%4 !== 0 // 剩下的总数是4的倍数时,先拿肯定输
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/05/26/2019-05-26/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog