[leetcode]: 292. Nim Game

向右看齐 2022-06-16 01:09 135阅读 0赞

**1.题目描述**  
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.  
翻译：一堆石头n，两个人A,B依次拿（1/2/3个），两个人都一样聪明。轮到谁的时候拿完，谁赢。  
给定n，A先拿，问A是否能赢。  
例：n=4,无论A先拿1/2/3,剩下3/2/1,B都能一次拿完，B赢，A输。

**2.分析**  
不考虑太复杂的，简单的看，这是一个动态规划问题。有A,B两人，石头n个。A先拿。  
设isWin\[n\]为石头数量为n时，A是否能赢。  
所以动态规划的状态转移方程就是：

> isWin\[i\]=1,i<4  
> isWin\[i\] = !(isWin\[i - 1\] && isWin\[i - 2\] && isWin\[i -3\]), n>=4

如何理解：A可能拿1，2，3个，isWin\[i - 1\]代表石头数为i-1时B先拿，B能否赢。只要B不是三种情况下都赢，A就可能赢。

由于动态规划或者递归提交都会超时，所以最终solution是n%4  
自己算一算就明白了。

**3.代码**

bool canWinNim(int n,int m) {
        vector<bool> isWin(n+1,false);
        isWin[0] = true;
        isWin[1] = true;
        isWin[2] = true;
        isWin[3] = true;
        if (n >= 4) {
            for (int i = 4; i <= n; i++)
                isWin[i] = !(isWin[i - 1] && isWin[i - 2] && isWin[i - 3]);
        }
        return isWin[n];
    }