NimGame2 [source code]

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

    public boolean canWinNim(int n) {
        for (int i = 0; i<=n; i++) {
            if (i < 4) map.put(i, true);
            else if (!map.get(i-1) || !map.get(i-2) || !map.get(i-3)) map.put(i, true);
            else map.put(i, false);
        }
        return map.get(n);
    }

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

这个就是bottom-up用 iterative 重写之后的算法了.
需要总结的一点是,并不是所有的 recursion 都可以很方便的用 iterative 来改写. 但是 DP 的就可以,因为 DP 算法最后的核心就是要maintain this table,所以 bottom-up 的时候,直接想你应该怎么生成这个 table 就行了.

另外这个算法貌似还是不能跑1348820612,虽然不 overflow 了,但是好像应该是超时了.

另外这里这个 HashMap 是可以换成一个 array 的. 不过估计还是超时. 而且用 Array 有一个问题, 事先无法知道这个 array 应该有多大.

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