题目
题解
本题实际上是一个需要分析的数学题。如果第一时间没有发现规律的话，可以尝试先用递归法，暴力输出前几个，观察规律。
// 用本函数跑 1~100，找规律 public boolean canWin(int n) {
if (n <= 3) return true; // canWinNim(n-1), canWinNim(n-2), canWinNim(n-3) 只要有一个为false本轮就能赢 // 也就是说，除非都为true才返回false，否则本轮能赢返回true return !(canWin(n - 1) && canWin(n - 2) && canWin(n - 3)); } 输出结果如下。
这样，规律就显而易见了，即：每逢 4 的倍数返回 false，其余都返回 true。
为什么会出现这样的规律呢？实际上，是可以通过推理得到的：
面对4的整数倍的人，永远无法翻身，你拿N根对手就会拿4-N根，保证每回合共减4根，你永远对面4倍数，直到4。相反，如果最开始不是4倍数，你可以拿掉刚好剩下4倍数根，让他永远对面4倍数。
发现这个规律之后，本题就很简单了。代码如下：
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0; } } 
2021-11-16 二刷
题目
题解
DP空间超了，DP+空间优化时间超了，只能数学解法。。
class Solution {
public boolean canWinNim(int n) {
// Approach 1: Recursive, Brute Force // return process(n); // Approach 2: DP // if (n <= 3) return true; // boolean[] dp = new boolean[n + 1]; // dp[0] = false; // dp[1] = true; // dp[2] = true; // dp[3] = true; // for (int i = 4; i <= n; i++) {
// dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3]; // } // return dp[n]; // Approach 3: DP + Space optimization // if (n <= 3) return true; // boolean[] dp = new boolean[4]; // dp[0] = false; // dp[1] = true; // dp[2] = true; // dp[3] = true; // int i = 3; // while (i++ <= n) {
// dp[i % 4] = !dp[(i + 4 - 1) % 4] || !dp[(i + 4 - 2) % 4] || !dp[(i + 4 - 3) % 4]; // } // return dp[n % 4]; // Approach 4: 玄学 // 对dp数组[false, true, true, ture]进行滚动更新，当除了自己以外其他3个均为true时结果为false，否则结果为true // 所以，滚动更新了个寂寞，根本不需要更新 return n % 4 != 0; } // 还剩n个石子的情况下，当前玩家以先手姿态是否能赢 // public boolean process(int n) {
// if (n <= 0) return false; // else if (n <= 3) return true; // // 只要有一种方法让对方不能赢，那么我就能赢 // return !process(n - 1) || !process(n - 2) || !process(n - 3); // } } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233123.html原文链接：https://javaforall.net
