Lintcode 394. Coins in a Line

There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.

Could you please decide the first player will win or lose?

If the first player wins, return true, otherwise return false.

Example

Example 1:

Input: 1
Output: true

Example 2:

Input: 4
Output: true
Explanation:
The first player takes 1 coin at first. Then there are 3 coins left.
Whether the second player takes 1 coin or two, then the first player can take all coin(s) left.

Challenge

O(n) time and O(1) memory

Solution 1: DFS with memorization:

public class Solution {
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        if (n == 0) {
            return false;
        }
        
        int[] memo = new int[n + 1]; // -1 unvisited, 0 win, 1 lose
        memo[0] = 1;
        memo[1] = 0;
        
        for (int i = 2; i < n + 1; i++) {
            memo[i] = -1;
        }
        
        return firstWillWinHelper(n, memo);
    }
    
    private boolean firstWillWinHelper(int n, int[] memo) {
        if (memo[n] != -1) {
            return memo[n] == 0? true : false;
        }
        
        boolean canWin = !firstWillWinHelper(n - 1, memo) || 
                         !firstWillWinHelper(n - 2, memo);
        
        memo[n] = canWin ? 0 : 1;
        
        return canWin;
    }
}

Solution 2: DP Solution
dp[n + 1], where dp[i] means for i coins in a line, the first player can win? 

Code (Java):

public class Solution {
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        if (n == 0) {
            return false;
        }
        
        // dp[i] means for the i coins in a line, the first player can win
        //
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;
        dp[1] = true;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = !dp[i - 1] || !dp[i - 2];
        }
        
        return dp[n];
    }
}