Coins in a Line 394

Question

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 play will win or lose?

Example

n = 1, return true.

n = 2, return true.

n = 3, return false.

n = 4, return true.

n = 5, return true.

Challenge

O(n) time and O(1) memory

Solution

我的方法：谁走3谁就输。因此，如果n能被3整除，则不管play1每次走几步，play2总能逼迫他走3，所以play1一定输，反之则play2一定输。结果是对的，但是没法证明。

DP：记忆化搜索。

假设在这一步我们取1个，则对手有两种选择：取1个或者2个。所以若n-2(我们1对手1)以及n-3（我们1对手2）都能获胜，则我们一定能获胜。

假设在这一步我们取2个，则对手有两种选择：取1个或者2个。所以若n-3(我们2对手1)以及n-4（我们2对手2）都能获胜，则我们一定能获胜。

只要上面两种情况有一种发生，则我们一定能获胜，反之则不能。

这里其实还可以考虑若n－1（我们取1个）和n－2（我们取2个）都不能获胜（即对手一定不能获胜），则我们一定获胜。但是会造成递归过深而爆栈。

代码如下：

time O(1) space O(1)

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) {
        // write your code here
        if(n <= 0){
            return false;
        }

        if(n % 3 != 0){
            return true;
        }
        return false;
    }
}

DP

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) {
        // write your code here
        // if(n % 3 != 0){
        //     return true;
        // }
        // return false;

        boolean[] dp = new boolean[n + 1];
        boolean[] visit = new boolean[n + 1];

        return search(n, dp, visit);
    }

    private boolean search(int n, boolean[] dp, boolean[] visit){
        if(visit[n]){
            return dp[n];
        }

        if(n == 0){
            dp[n] = false;
        }else if (n == 1 || n == 2){
            dp[n] = true;
        }else{
            if((search(n - 2, dp, visit) && search(n - 3, dp, visit)) || (search(n -3, dp, visit) && search(n - 4, dp, visit))){
                dp[n] = true;
            }else{
                dp[n] = false;
            }
        }

        visit[n] = true;
        return dp[n];
    }
}