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

Analysis

We need to identify the 4 elements to solve a DP problem. State, Function, Initiation and Answer.

State: dp[x] is a boolean array indicating whether the player will win(T) or lose(F) when facing x elements.

Function: a simple analysis should show that dp(i) is depending on (dp(i-4) && dp(i-3)) || (dp(i-3) && dp(i-2)).

Initialization: dp(0) = F, dp(1) = T, dp(2) = T, dp(3) = F and dp(4) = T. Looking at the function to see to each index the initialization is enough.

Answer: dp(n)

Performance can be improvely greatly when using memorizatoin.

Solution

int[] visited;

public boolean firstWillWin(int n) {
    visited = new int[n+1];
    Arrays.fill(visited, -1);
    return helper(n);
}

public boolean helper(int n){
    if (visited[n] != -1){
        return visited[n] == 2;
    }

    if (n == 0){
        return false;
    }else if (n == 1){
        return true;
    } else if (n == 2){
        return true;
    } else if (n == 3){
        return false;
    } else if (n == 4){
        return true;
    } else if (n == 5){
        return true;
    } else {
        boolean res = ((helper(n-2) && helper(n-3)) || (helper(n-3) && helper(n-4)));
        if (res){
            visited[n] = 2;
        } else {
            visited[n] = 1;
        }
    }

    if (visited[n] == 2){
        return true;
    } else {
        return false;
    }
}

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

Example

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

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

Analysis:

My analysis for DP has improved when solving this problem. Similar analysis can be carried out to show that the

Function:

int left = min(f(i-2), f(i-3)) 
int right = min(f(i-3), f(i-4)
f(i) = max( left + A[i], right + A[i] + A[i-1]);

Initialization:

f(0) = 0
f(1) = A[0]
f(2) = A[2] + A[1]
f(3) = A[2] + A[1]

One trap here is that the coins are taken away from the left side, unlike the first question where the coins are taken away from the right.

Solution

 public boolean firstWillWin(int[] values) {
    if (values.length == 1){
        return true;
    }

    int sum = 0;
    for (int i = 0; i < values.length; i++){
        sum += values[i];
    }   

    int[] dp = new int[values.length+1];

    helper(values, dp, dp.length-1);
    return dp[dp.length-1] > sum /2;
}

public int helper(int[] values, int[] dp, int n){
     if (dp[n] != 0){
         return dp[n];
     }

     if (n == 0){
         dp[0] = 0;
     } else if (n == 1){
         dp[1] = values[values.length-1];
     }else if (n == 2){
         dp[2] = values[values.length-2] + values[values.length-1];
     } else if (n == 3){
         dp[3] = values[values.length-3] + values[values.length-2];
     } else {
         int left = Math.min(helper(values, dp, n-2) + values[values.length-1-n+1], helper(values, dp, n-3) + values[values.length-1-n+1]);
         int right = Math.min(helper(values, dp, n-3) + values[values.length-1-n+2] + values[values.length-1-n+1], helper(values, dp, n-4) + values[values.length-1-n+2] + values[values.length-1-n+1]);
         dp[n] = Math.max(left, right);
     }

     return dp[n];
}

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.

Analysis

If we still use one dimension array F(i) to represent i coins in the array, we will have trouble to identify exactly which i coins because the coins can be taken from both sides. A two dimensation array should be used to represent an interval of coins.

F(i)(j).

Function:

f(i,j) = max(min(f(i+1,j-1), f(i+2,j)+A[i]), min(f(i,j-2), f(i+1,j-1)) + A[j]))

Initialization:

f(0,0) = A[0]
f(1,1) = A[1]
f(2,2) = A[2]
f(3,3) = A[3]]

Solution

public boolean firstWillWin(int[] values) {
    if (values.length == 0){
        return false;
    }

    int sum = 0;
    for (int i = 0; i < values.length; i++){
        sum += values[i];
    }

    int[][] dp = new int[values.length][values.length];

    helper(values, dp, 0, values.length-1);
    return dp[0][values.length-1] > sum /2;
}

public int helper(int[] values, int[][] dp, int start, int end){
    if (dp[start][end] != 0){
        return dp[start][end];
    }

    if (end - start == 1){
        dp[start][end] = Math.max(helper(values, dp, start, start), helper(values, dp, end, end));
    } else if (start == end){
        dp[start][end] = values[start];
    } else {
        int left = helper(values, dp, start+2,end);
        int mid = helper(values, dp, start+1, end-1);
        int right = helper(values, dp, start, end-2);
        dp[start][end] = Math.max(Math.min(left, mid) + values[start],Math.min(mid, right) + values[end]);
    }

    return dp[start][end];
}