[LintCode] 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 the first player will win or lose?

Example

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

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

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。

请判定 第一个玩家 是输还是赢？

样例

给定数组 A = [1,2,2], 返回 true.

给定数组 A = [1,2,4], 返回 false.

http://www.lintcode.com/en/problem/coins-in-a-line-ii/

贪心法，对于双方玩家都先取一枚硬币，在决定要不要取第二枚硬币时，比较第二枚硬币和第二枚硬币之后的一枚硬币的大小，即values[i]与values[i+1]的大小，如果values[i]大，就取走，否则就留下。

下面是AC代码。至于正确性的证明，唔，让我先想一想，想明白了再回来补上~

 1 class Solution {
 2 public:
 3     /**
 4      * @param values: a vector of integers
 5      * @return: a boolean which equals to true if the first player will win
 6      */
 7     bool firstWillWin(vector<int> &values) {
 8         // write your code here
 9         int val1 = 0, val2 = 0;
10         bool turn = true;
11         for (int i = 0; i < values.size(); ) {
12             int &val = turn ? val1 : val2;
13             val += values[i++];
14             if (i < values.size() && (i + 1 >= values.size() || values[i] >= values[i + 1])) {
15                 val += values[i++];
16             }
17             turn = !turn;
18         }
19         return val1 > val2;
20     }
21 };

上面的贪心应该不对，下面的dp肯定是正确的。dp[idx]表示从第idx个硬币到最后一个硬币所能拿到的最大value，因为对手也取最优策略，所以每次取完后要对手会留给我们两种方案，我们只能取价值更小的一种方案。

 1 class Solution {
 2 public:
 3     /**
 4      * @param values: a vector of integers
 5      * @return: a boolean which equals to true if the first player will win
 6      */
 7     bool firstWillWin(vector<int> &values) {
 8         // write your code here
 9         int n = values.size();
10         vector<int> dp(n + 1, -1);
11         int sum = 0;
12         for (auto v : values) sum += v;
13         return sum < 2 * dfs(dp, values, n);
14     }
15     int dfs(vector<int> &dp, vector<int> &values, int idx) {
16         if (dp[idx] != -1) return dp[idx];
17         int n = values.size();
18         if (idx == 0) {
19             dp[idx] = 0;
20         } else if (idx == 1) {
21             dp[idx] = values[n-1];
22         } else if (idx == 2) {
23             dp[idx] = values[n-1] + values[n-2];
24         } else if (idx == 3) {
25             dp[idx] = values[n-2] + values[n-3];
26         } else {
27             int take1 = min(dfs(dp, values, idx - 2), dfs(dp, values, idx - 3)) + values[n-idx];
28             int take2 = min(dfs(dp, values, idx - 3), dfs(dp, values, idx - 4)) + values[n- idx + 1] + values[n - idx];
29             dp[idx] = max(take1, take2);
30         }
31         return dp[idx];
32     }
33 };