NimGame [source code]

public class NimGame {
    public Map<Integer, Boolean> map = new HashMap<>();

    public boolean canWinNim(int n) {
        if(n <= 3) return true;
        Boolean result = map.get(n);
        if (result != null) return result;
        boolean resultCalculated = !canWinNim(n-1) || !canWinNim(n-2) || !canWinNim(n-3);
        map.put(n, resultCalculated);
        return resultCalculated;
    }

    public static void main(String[] arg) {
        NimGame tester = new NimGame();
        int input1 = 5;
        int input2 = 1348820612;
        int input3 = 2000;
        int input4 = 20000;
        System.out.println(tester.canWinNim(1348820612));
        // for (int i = 1; i < 1000; i++) System.out.println(tester.canWinNim(i));
    }
}

Fail1:
Runtime Error Message:
Line 4: java.lang.StackOverflowError
Last executed input:
1348820612

首先这个问题本身的算法是很简单的,一个最直白的 DP 就解决了. 但是 LC 在这个问题上还是下了坑, DP本身的效率问题我也很清楚;果然OJ 还是摆了一个很大的
case,结果直接 overflow;
那么既然 OJ 故意摆一个这么大的 n,其实就是故意筛除所有不够快的方法.
我一开始的写法是:
public boolean canWinNim(int n) {
if(n <= 4) return true;
else return (canWinNim(n-1) || canWinNim(n-2) || canWinNim(n-3));
}

后来才想到这样写是有问题的,就算是算法课上学的 DP,也是要用 memoization 的.
然而加了 memoization 还是不行,就连20000都 hold 不住.

如果有人告诉你有1348820612这么大的 n,那基本就是暗示你,比如要做到O(n).
当然这个问题真正的方法怎么做其实我是知道的,这个还一个非常非常明显的 pattern 题.

it's official, 能帮 DP 做的优化基本都做完了,然而还是 overflow,所以这题基本是只能靠 pattern 来做了;
当然正确答案是很简单的: return !(n%4==0);
但是我觉得还是应该借这个题目好好理解 DP 的过程.
需要注意的一点是:
boolean resultCalculated = !canWinNim(n-1) || !canWinNim(n-2) || !canWinNim(n-3);
这一行的逻辑,还是有点绕人的,一开始我写成了: !(..||..||..),这个明显是没有好好想通这个问题.

问了一下 guoye,这里虽然说最后的复杂度是 n,但是还是 overflow,是因为栈的深度是有限的,几千层的recursion 就不得了了,并不是因为复杂度的问题(其实你应该想得到啊, 超时的话 OJ 给的是另外一个信息);

TODO:看看这个算法能不能用bottom-up来写,按说应该是可以的.

Problem Description

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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:55.18%
Contributor: LeetCode
Companies
adobe
Related Topics
brainteaser
Similar Questions
Flip Game II