leetcode 877

问题

Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

1
2
3
4
5
6
7
8
Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

Note:

  1. 2 <= piles.length <= 500
  2. piles.length is even.
  3. 1 <= piles[i] <= 500
  4. sum(piles) is odd.

分析

思路1: 动态规划，令 $f(i,j)$ 表示从 $a[i..j]$ 这个范围内，先行者能够获得的最大的石块数量。$sum(i, j)$ 表示 $a[i..j]$ 中所有元素的和。则有状态转移方程如下：
$$
f(i,j) = max \{a[i]+sum(i+1,j)-f(i+1,j), a[j]+sum(i,j-1)-f(i,j-1)\};
$$
初始状态令 $f(i,j) = a[i]$. 以区间长度来作为DP的阶段，最终求出$f(0,n-1)$ 的值，然后判断其是否能够大于$sum(0,n-1) $ 的一半。

思路2: 采用数学的方法。在这道题目中石堆的总数是偶数个，并且所有石子个个数是奇数个，那么就只存在，所有下标为偶数的石堆中所包含的石子的总和大于所有下标为奇数的石堆中所有石子的总和，要么小于。那么对于Alice而言，才去某种方案，他总能获取到所有下标为奇数的石堆，或者总能获取到下标为偶数的石堆。所以说，Alice一定是可以赢的。比如让Alice选择的所有石堆都是下标为偶数的石堆，在所有石堆中，Alice先行选择，Alice选择了下标为0的石堆，那么Lee的选择只能从下标为奇数的石堆中进行选择了。那么接下来，Alice又存在了两种选择，下标为偶数的石堆或者下标为奇数的石堆，这么在这个时候，我们再让Alice从下标为偶数的石堆中进行选择，于是Lee又只能从下标为奇数的石堆中进行选择了。依次类推，Alice所有选择的石堆都将是下标为偶数的石堆。同理，Alice也可以选择所有下标都为奇数的石堆。因此，Alice稳赢。

代码1

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
32
// DP solution
class Solution {
public:
    inline int getsum(vector<int> &sum, int lo, int hi) {
        if (lo == 0)
            return sum[hi];
        return sum[hi] - sum[lo-1];
    }
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        vector<int> sum(n, 0);
        sum[0] = piles[0];
        for (int i = 1; i < n; ++i) {
            sum[i] = sum[i-1] + piles[i];
        }
        
        for (int i = 0; i < n; ++i) {
            dp[i][i] = piles[i];
        }
        
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i+k-1 < n; ++i) {
                int j = i+k-1;
                dp[i][j] = max(getsum(sum, i+1, j) - dp[i+1][j] + piles[i],
                              getsum(sum, i, j-1) - dp[i][j-1] + piles[j]);
            }
        }
        
        return dp[0][n-1] >= (sum[n-1]+1)/2;
    }
};

代码2

1
2
3
4
5
6
7
// Math
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};