Leetcode PHP题解--D64 292. Nim Game

D64 292. Nim Game

题目链接

292. Nim Game

题目分析

假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。

同时假设你和你的朋友都足够聪明，每次都能采取最优策略。

现给定一个石头数量，判断你最终是否能取得胜利。

思路

我们先从少一点开始推广到n个石头。

如果有1～3颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下1

假设有4颗石头。

你拿1颗，会剩下3颗。对方全拿， 对方赢 。

你拿2颗，会剩下2颗。对方全拿， 对方赢 。

你拿3颗，会剩下1颗。对方全拿， 对方赢 。

即，怎么拿都是你输。

假设有5颗石头。

你拿1颗，会剩下4颗。

对方拿走1颗，剩下3颗给你，你全拿，你赢。

对方拿走2颗，剩下2颗给你，你全拿，你赢。

对方拿走3颗，剩下1颗给你，你全拿，你赢。

你拿2颗，会剩下3颗。对方全拿， 对方赢 。

你拿3颗，会剩下2颗。对方全拿， 对方赢 。

因此，这一轮你会选择拿1颗，剩下4颗。

假设有6颗石头。

你拿1颗，会剩下5颗。

对方拿走1颗，剩下4颗给你，参考一开始就只有4颗的情况， 对方赢 。

对方拿走2颗，剩下3颗给你，你全拿，你赢。

对方拿走3颗，剩下2颗给你，你全拿，你赢。

你拿2颗，会剩下4颗。

对方拿走1颗，剩下3颗给你，你全拿，你赢。

对方拿走2颗，剩下2颗给你，你全拿，你赢。

对方拿走3颗，剩下1颗给你，你全拿，你赢。

你拿3颗，会剩下3颗。对方全拿， 对方赢 。

因此，这一轮你会选择拿2颗，剩下4颗。

假设有7颗石头。

你拿1颗，会剩下6颗。

对方拿走1颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。

对方拿走2颗，剩下4颗给你， 对方赢 。

对方拿走3颗，剩下3颗给你，你全拿，你赢。

你拿2颗，会剩下5颗。

对方拿走1颗，剩下4颗给你， 对方赢 。

对方拿走2颗，剩下3颗给你，你全拿，你赢。

对方拿走3颗，剩下2颗给你，你全拿，你赢。

你拿3颗，会剩下4颗。

对方拿走1颗，剩下3颗给你，你全拿，你赢。

对方拿走2颗，剩下2颗给你，你全拿，你赢。

对方拿走3颗，剩下1颗给你，你全拿，你赢。

因此，这一轮你会选择拿3颗，剩下4颗。

假设有8颗石头。

你拿1颗，会剩下7颗。

对方拿走1颗，剩下6颗给你，参考一开始就只有6颗的情况，你赢。

对方拿走2颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。

对方拿走3颗，剩下4颗给你， 对方赢 。

你拿2颗，会剩下6颗。

对方拿走1颗，剩下5颗给你，你赢。

对方拿走2颗，剩下4颗给你， 对方赢。

对方拿走3颗，剩下3颗给你，你全拿，你赢。

你拿3颗，会剩下5颗。

对方拿走1颗，剩下4颗给你， 对方赢。

对方拿走2颗，剩下3颗给你，你全拿，你赢。

对方拿走3颗，剩下2颗给你，你全拿，你赢。

因此，必输无疑。

我们可以得出规律。当剩下的石头为4的整数倍、双方都采取最优策略时，先下手的一方为输家。

因此这个题目就很简单了，只要判断给定的数字是否是4的整数倍即可。

最终代码

<?php
class Solution {

    /**
     * @param Integer $n
     * @return Boolean
     */
    function canWinNim($n) {
        return $n%4!=0;
    }
}

若觉得本文章对你有用，欢迎用 爱发电 资助。