Leetcode 292. Nim 游戏 解题思路及C++实现

方法一：规律

解题思路：

n从1开始增加，可以发现，当 n 是 4 的倍数的时候，就是false。

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

 

方法二：动态规划

解题思路：

因为题中说是两个聪明人轮流拿石头，每一步都是最优解，所以，动态规划的状态转移方程是：

dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]

就说是，在有i个石头的时候，我如果想赢，必须是对方在面对 i - 1, i - 2, i - 3个石头的时候都是输的。

但是动态规划会报 超出时间限制 的错误。

 

class Solution { public:bool canWinNim(int n) {if(n > 0 && n < 4) return true;vector<bool> dp(n, true);for(int i = 3; i < n; i++){dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3];}return dp[n-1];} };

 

 

总结

以上是生活随笔为你收集整理的Leetcode 292. Nim 游戏 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。