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

Example

n =1, returntrue.

n =2, returntrue.

n =3, returnfalse.

n =4, returntrue.

n =5, returntrue.

public boolean firstWillWin(int n) {
    if(n <= 0) {
        return false;
    }
    boolean[] dp = new boolean[n + 1];
    dp[0] = false;
    dp[1] = true;
    if(n >= 2) {
        dp[2] = true;
    }
    if(n >= 3) {
        dp[3] = false;
    }
    for(int i = 4; i <= n; i++) {
        //先手取硬币的人剩1个或2个，并且其状态取决于上一个玩家，使他落在i - 1和i - 2的范围内，则我们i肯定是赢得，对应到先手的玩家则是下面的转移方程
        dp[i] = (dp[i - 2] && dp[i - 3]) || (dp[i - 3] && dp[i - 4]);
    }
    return dp[n];
}

public boolean firstWillWin(int n) {
    if(n <= 0) {
        return false;
    }
    boolean[] dp = new boolean[n + 1];
    dp[0] = false;
    dp[1] = true;
    if(n >= 2) {
        dp[2] = true;
    }
    if(n >= 3) {
        dp[3] = false;
    }
    for (int i = 3; i <= n; i++) {
        //当期取硬币的人剩i - 1个硬币或i- 2个硬币输了，那么下一个人必胜
        if(!dp[i - 1]  || !dp[i - 2]) {
            dp[i] = true;
        }        
    }
    return dp[n];
}

Coins in a Line II

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

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

Example

Given values array A =[1,2,2], returntrue.

Given A =[1,2,4], returnfalse.

public boolean firstWillWin(int[] A) {
    if(A == null || A.length == 0) {
        return false;
    }
    int n = A.length;
    if(n <= 2) {
        return true;
    }
    int[] dp = new int[n + 1];
    dp[n] = 0;
    dp[n - 1] = A[n - 1];
    dp[n - 2] = A[n - 2] + A[n - 1];
    dp[n - 3] = A[n - 3] + A[n - 2];
    for(int i = n - 4; i >= 0; i--) {
        dp[i] = A[i] + Math.min(dp[i + 2], dp[i + 3]);
        dp[i] = Math.max(dp[i], A[i] + A[i + 1] + Math.min(dp[i + 3], dp[i + 4]));
    } 
    int sum = 0;
    for(int val : A) {
        sum += val;
    }
    return dp[0] > sum - dp[0];
}

Coins in a Line III

There are _n _coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

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

Example

Given array A =[3,2,2], returntrue.

Given array A =[1,2,4], returntrue.

Given array A =[1,20,4], returnfalse.

public boolean firstWillWin(int[] values) {
    if(values == null || values.length == 0) {
        return false;
    }
    int n = values.length;
    int[][] dp = new int[n][n];
    int[] sum = new int[n + 1];
    sum[0] = 0;
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + values[i - 1];
    }
    for(int i = 0; i < n; i++) {
        dp[i][i] = values[i];
    }
    for(int len = 2; len <= n; len++) {
        for(int i = 0; i < n; i++) {
            int j = i + len - 1;
            if(j >= n) {
                break;
            }
            int sums = sum[j + 1] - sum[i];
            dp[i][j] = Math.max(sums - dp[i + 1][j], sums - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] > sum[n] / 2;
}