Lintcode DP Coins in a Line

###Task1 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?

Have you met this question in a real interview? Yes 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

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

###Task2

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?

Have you met this question in a real interview? Yes Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

###Java

public class Solution {
    /**
     * @param values: an array of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        // write your code here
        if (values == null || values.length == 0) {
            return false;
        }
        if (values.length <= 2) {
            return true;
        }
        int n = values.length;
        int[] dp = new int[n + 1];
        dp[n] = 0;
        dp[n - 1] = values[n - 1];
        dp[n - 2] = values[n - 2] + values[n - 1];
        dp[n - 3] = values[n - 3] + values[n - 2];
        
        for (int i = n - 4; i >= 0; i--) {
            dp[i] = values[i] + Math.min(dp[i + 1 + 1], dp[i + 1 + 2]);
            dp[i] = Math.max(dp[i], values[i] + values[i + 1] + Math.min(dp[i + 2 + 1], dp[i + 2 + 2]));
        }
        int sum = 0;
        for (int a: values) {
            sum += a;
        }
        return dp[0] > sum - dp[0];
        
    }
}

###Points

• DP

• 1st: We take only one coins which has values[i], then the other player will give us a choices between min(dp[i+2], dp[i+3]), ( she takes one or two coins).

  2nd: Same as above analyze, we take two coins, then the max value we will get is values[i] + values[i+1] + min(dp[i+3],dp[i+4]). Finally, if dp[0] > sum - dp[0] we can win or we lose.(sum is the total value of the coins, dp[0] means the maximum possible value we can get from first coin to the last one).