Coins in a Line II

Question

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], return true.

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

Tags

Dynamic Programming Array Game Theory

Related Problems

Hard Coins in a Line III 30 % Medium Coins in a Line

Analysis

动态规划4要素

  • State:

    • dp[i] 现在还剩i个硬币，现在当前取硬币的人最后最多取硬币价值

  • Function:

    • i 是所有硬币数目

    • sum[i] 是后i个硬币的总和

    • dp[i] = sum[i]-min(dp[i-1], dp[i-2])

  • Intialize:

    • dp[0] = 0

    • dp[1] = coin[n-1]

    • dp[2] = coin[n-2] + coin[n-1]

  • Answer:

    • dp[n]

可以画一个树形图来解释：

                  [5, 1, 2, 10] dp[4]
        (take 5) /             \ (take 5, 1)
                /               \
        [1, 2, 10] dp[3]         [2, 10] dp[2]
(take 1) /     \ (take 1, 2)  (take 2) / \ (take 2, 10)
        /       \                     /   \
  [2, 10] dp[2]  [10] dp[1]     [10] dp[1] [] dp[0]

也就是说，每次的剩余硬币价值最多值dp[i]，是当前所有剩余i个硬币价值之和sum[i]，减去下一手时对手所能拿到最多的硬币的价值，即 dp[i] = sum[i] - min(dp[i - 1], dp[i - 2])

Solution

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) {
        if (values == null || values.length == 0) {
            return false;
        }
        int n = values.length;
        int[] dp = new int[n + 1];
        boolean[] flag = new boolean[n + 1];

        int[] sum = new int[n + 1];
        int total = 0;
        sum[0] = 0;
        for (int i = n - 1; i >= 0; i--) {
            sum[n - i] = sum[n - i - 1] + values[i];
            total += values[i];
        }

        return search(n, n, dp, flag, values, sum) > total / 2;
    }
    public int search(int i, int n, int[] dp, boolean[] flag, int[] values, int[] sum) {
        if (flag[i] == true) {
            return dp[i];
        }
        if (i == 0) {
            dp[i] = 0;
        } else if (i == 1) {
            dp[i] = values[n - 1];
        } else  if (i == 2) {
            dp[i] = values[n - 1] + values[n - 2];
        } else {
            dp[i] = sum[i] - Math.min(search(i - 1, n, dp, flag, values, sum), search(i - 2, n, dp, flag, values, sum));
        }
        flag[i] = true;
        return dp[i];
    }
}

Reference

PreviousCoins in a LineNextCoins in a Line III

Last updated