Using backtrace and dynamic programming.


  • 9
    Z

    The basic idea is very simple. if the opponent can win , then the player will lose. The condition is that No matter how many stones the player move, the opponent will win. So the code is

    if(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3)) return false;
    

    Here are the two methods.But they both cannot pass the large test case.

    public boolean canWinNim(int n) {
        // 1 2 3 (4) 5 6 7 (8) 9 10 11 (12)
        if(n <= 0) return false;
        if(n == 1 || n == 2 || n== 3) return true;
        if(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3)) return false;
        return true;
    }
    
    
    public boolean canWinNim(int n) {
        // 1 2 3 (4) 5 6 7 (8) 9 10 11 (12)
        // add this line to pass large test case
        if(n >= 134882061) return n%4 != 0;
        boolean res = true;
        boolean fir = true;
        boolean sec = true;
        boolean thir = true;
        for(int i=4;i<=n;i++){
            res = (fir && sec && thir) ? false:true;
            fir = sec;
            sec = thir;
            thir = res;
        }
        return res;
    }

  • 0
    M

    it will use more memory,its time efficiency is not high!
    Are you sure that it can pass through OJ's checked?


  • 0
    Z

    I think the logic is right. Why these down votes? I add a new line of code to pass the large test case.


  • 2
    Y

    the logic is quite clear, and the method is more general. good job.


  • 0
    H

    I think people just want a more specific answer. The for loop works, but an O(1) answer exists.


  • 0
    W

    agreed. it is a good answer although more efficient one exists


  • 0
    T

    I think this could not be called dp, possible.. I am little confused why this is a dp, because it is an observation, that is, after three continous lose, then a win.


  • 1
    S

    This is the answer I would like to see. The important thing we need to build is not using math to solve problems, let leave this to the researchers... But use general "Algorithm Thoughts" to solve general problems. Good job, but, any chance to solve the special case?


  • 0
    H

    @zq670067
    Clear code. However the logic may be better if change the for loop like this:

    public boolean canWinNim(int n) {
            // 1 2 3 (4) 5 6 7 (8) 9 10 11 (12)
            // add this line to pass large test case
            if(n >= 134882061) return n%4 != 0;
            boolean res = true;
            boolean fir = true;  // for i = 4, the result of the other player when I choose to move one stone
            boolean sec = true;
            boolean thir = true;
            for(int i=4;i<=n;i++){
                res = (fir && sec && thir) ? false:true;
                thir = sec;  // moving (i + 1) stones for next iteration is the same as moving (i)  stones for this iteration
                sec = fir;
                fir = res;
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.