Java DP solution with explanation (not acceptable but worth to share)


  • 4
    L
    public boolean canWinNim(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n should be greater than 0.");
        }
    
        // For stones less than 4, we are already win, cause we can just take all the stones.
        if (n < 4) {
            return true;
        }
    
        // Then, think about the question in this way: 
        // after choosing 1 ~ 3 stones in the first round, 
        // can we left AT LEAST ONE dead-end to another player?
    
        // For 4 stones, if we choose 1 stone, there are 3 stones left;
        // choose 2 stones, 2 stones left;
        // choose 3 stones, 1 stone left. 
        // This is a bad situation for us, but a good news for another player,
        // because 1, 2, 3 stones are all not dead-ends for him.
    
        // So to determine if we can win the game, we only need to care about if we can left AT LEAST ONE dead-end at first round.
    
        // For example:
        //    5 stones: choose 1 stone, left 4 stones, 4 stones is a dead-end so we win;
        //    6 stones: choose 2 stones, left 4 stones, win again.
        //    7 stones: choose 3 stones, left 4 stones, win again.
        //    8 stones: after choosing 1, 2, 3 stones, we left either 5, 6, or 7 stones, and none of them are dead-ends, so we cannot win the game.
        //    9 stones: we choose 1 stone, left 8 stones, 8 stones is a dead-end so we win...
        //    and so on...
        
        // So here comes the DP solution.
        boolean[] dp = new boolean[n + 1];
        dp[1] = true;
        dp[2] = true;
        dp[3] = true;
        dp[4] = false;
        for (int i = 5; i <= n; i++) {
            // We choose stones from 1 to 3.
            // If there is at least one dead-end left, then we can be sure that we can win at `i`;
            // otherwise we can just left it as false as a dead-end by default.
            for (int j = 1; j <= 3; j++) {
                if (!dp[i - j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

  • 1
    S

    I think it is enough to maintain the last three status in the code

    public class Solution {
        public boolean canWinNim(int n) {
            boolean[] dp = {true,true,true};
            for(int i=4;i<=n;i++){
                if(dp[0] && dp[1] && dp[2]){
                    dp[0] = dp[1];
                    dp[1] = dp[2];
                    dp[2] = false;
                }
                else{
                    dp[0] = dp[1];
                    dp[1] = dp[2];
                    dp[2] = true;
                }
            }
            return dp[2];
        }
    }
    

    not acceptable though.


  • 0
    A
    public class Solution {
        public boolean canWinNim(int n) {
            if (n <= 3) {
                return true;
            }
            boolean[] p = new boolean[4];
            p[0] = p[1] = p[2] = true;
            for (int i = 3; i < n; i++) {
                p[i%4] = !(p[(i-1)%4]&&p[(i-2)%4]&&p[(i-3)%4]);
            }
            return p[(n-1)%4];
        }
    }
    

    value copy is not necessary


  • 0
    F

    I can not eally understand your solution?


  • 0
    B

    both players play optimally, so if one of three previous dp is true that means he can get manage to get to that state too. So you should strictly check if all of the three previous dp is not true.

    for (int i = 5; i <= n; i++) {

    bool ret = true;

    for (int j = 1; j <= 3; j++) {

    if (dp[i - j]) {

    ret = false;

    }

    }

    dp[i] = ret;

    }

    But I am afraid this solution gets run out of both time and memory even though it is a nice solution.


Log in to reply
 

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