LeetCode 292 Nim Game

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

概述

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

反向思考

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

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

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

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

如何营造 57 颗石子的局面呢?让对手面对 8 颗石子,无论他怎么拿,都会给我剩下 57 颗,我就能赢。

这样一直循环下去,我们发现只要踩到 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];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/