leetcode 877 Stone Game 题解

发表于

国庆长假，水一题

题目

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.

解法一

第一种解法是使用动态规划，注意到每次Alex和Lee的操作都是从piles的头或尾取走一个最大的数，那么就可以把问题分解到多个子问题上分别来解决。

先构建一个数组存储piles的备份，以及一个二维数组存储各个子问题的解：

1
2
3
4
5
6
7
8
9
vector<vector<int>> dparr;
vector<int> p;
bool stoneGame(vector<int>& piles) {
    p = piles;
    int size = piles.size();
    vector<vector<int>> tmp(size, vector<int>(size, 0));
    dparr = tmp;
    return dp(0, size - 1) > 0;
}

下面是dp的具体实现，这里将Lee的操作视为从Alex的得分中扣除，最后只要Alex的得分大于零则Alex胜利：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dp(int low, int high){
    if(low == high){
        return 0;
    }
    if(dparr[low][high] != 0){	//避免重复计算
        return dparr[low][high];
    }
    int res = 0;
    if((high - low + 1) % 2 == 0){  //Alex
        res = max(dp(low + 1, high) + p[low], dp(low, high - 1) + p[high]);
    } 
    else{	//Lee
        res = min(dp(low + 1, high) - p[low], dp(low, high - 1) - p[high]);
    }
    dparr[low][high] = res;
    return res;
}

解法二

让我们回到问题：数组中一共有偶数个元素，Alex先选，Lee后选。那么假设数组有2n个元素，如果Alex第一次选择了元素1，则Lee可以选择2或2n，在之后Alex可以选择3、2n或者2、2n-1，以此类推。也就是说，可以保证Alex一定能够选到所有奇数位置的元素或是所有偶数位置的元素，那么只要一开始知道奇数位置元素之和与偶数位置元素之和哪个更大，就能保证Alex胜利，所以实际上这道题我们只需要：

1
return true;

就能够通过。