LeetCode 292 Nim Game

    
        标签：
        
            数学类题目
        
            LeetCode
        
    发布于：2022-03-01 11:20:58
    编辑于：2022-03-01 11:29:38
    浏览量：971

概述

https://leetcode.com/problems/nim-game/

反向思考

https://labuladong.gitee.io/algo/4/30/124/#一nim-游戏

如果我能赢，那么最后轮到我取石子的时候必须要剩下 1~3 颗石子，这样我才能一把拿完。

如何营造这样的一个局面呢？显然，如果对手拿的时候只剩 4 颗石子，那么无论他怎么拿，总会剩下 1~3 颗石子，我就能赢。

如何逼迫对手面对 4 颗石子呢？要想办法，让我选择的时候还有 5~7 颗石子，这样的话我就有把握让对方不得不面对 4 颗石子。

如何营造 5~~7 颗石子的局面呢？让对手面对 8 颗石子，无论他怎么拿，都会给我剩下 5~~7 颗，我就能赢。

这样一直循环下去，我们发现只要踩到 4 的倍数，就落入了圈套，永远逃不出 4 的倍数，而且一定会输。

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4;
    }
};

动态规划法

芜湖，MLE 了，LeetCode 给了个巨大的数：

class Solution {
public:
    vector<int> dp;
    bool canWinNim(int n) {
        dp.resize(n+1, -1);
        return helper(n);
    }
    
    bool helper(int n) {
        if (n <= 3) return true;
        if (dp[n] != -1) return dp[n];
        dp[n] = !helper(n-1) || !helper(n-2) || !helper(n-3);
        return dp[n];
    }
};

Links: leetcode-292-nim-game