Coins-in-Line

发表于 更新于

Description

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?

Examples

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

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

Thinking

这里设 dp[i] 表示从i到n能取到的最大值。

每次先手可以取1或2枚硬币，使自身的选择价值最大，同理对手的选择将使先手接下来能选的硬币价值最小。

1
2
3
4
int pick1 = values[i] + min(dp[i+1], dp[i+2]); // 取一枚
int pick2 = values[i+1] + values[i+2] + min(dp[i+3], dp[i+4]); // 取两枚
dp[i] = max(pick1, pick2);

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool firstWillWin(vector<int> values) {
        if (values.size() <= 2)
            return true;

        int sum = 0, len = values.size();
        vector<int> dp(values.size()+2, 0);

        for (int i=0; i<values.size(); ++i)
            sum += values[i];

        dp[len-1] = values[len-1];
        dp[len-2] = values[len-1] + values[len-2];
        dp[len-3] = values[len-2] + values[len-3];

        for (int i = len-4; i >= 0; --i) {
            int pick1 = values[i] + min(dp[i+2], dp[i+3]);
            int pick2 = values[i] + values[i+1] + min(dp[i+3], dp[i+4]);
            dp[i] = max(pick1, pick2);
        }

        return sum - dp[0] < dp[0];
    }
};