Coins in a Line II

Coins in a Line II

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?

Example:

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

分析：

假设dp[i] 表示从i到end能取到的最大value。

当我们走到 i 时，有两种选择：(1) 取values[i]。(2) 取values[i] + values[i+1]。

  1. 如果取values[i]，对手的选择有values[i+1]或者values[i+1] + values[i+2]剩下的最大总value分别为dp[i+2] 或 dp[i+3]，对手也是理性的所以要让我们得到最小value。所以value1 = values[i] + min(DP[i+2], DP[i+3])。

  2. 如果取values[i]和values[i+1]，同理value2 = values[i] + values[i+1] + min(dp[i+3], dp[i+4])。

最后状态转移方程：dp[i] = max(value1, value2)。

Code：

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
27
28
29
30
31
class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        if (values.size() < 3) return true;
        int len = values.size();
        vector<int> dp(len, 0);
        int total = 0;
        
        dp[len - 1] = values[len - 1];
        dp[len - 2] = values[len - 2] + values[len - 1];
        for (int i = len - 3; i >= 0; i--) {
            int a = i + 4 <= len -1 ? dp[i + 4] : 0;
            int b = i + 3 <= len -1 ? dp[i + 3] : 0;
            int c = i + 2 <= len -1 ? dp[i + 2] : 0;
            
            int value_take1coin = values[i] + min(b, c);
            int value_take2coins = values[i] + values[i + 1] + min(a, b);
            dp[i] = max(value_take1coin, value_take2coins);
        }
        
        for (int j = 0; j < len; j++) {
            total += values[j];
        }
        return dp[0] > (total - dp[0]) ? true : false;
    }
};