# 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

```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) {
        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

* [LeetCode Article: Coins in Line](http://articles.leetcode.com/coins-in-line/)
* [Dynamic Programming — Coin In a Line Game Problem](http://algorithms.tutorialhorizon.com/dynamic-programming-coin-in-a-line-game-problem/)
* [geeksforgeeks: Dynamic Programming | Set 31](http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/coins_in_a_line_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.