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.

相关题目: 486. Predict the Winner

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.

错误的思路

一开始以为可以用双指针的方式解决：每次贪心，选择从排在最前面和最后面的石头堆里选择数量较大的那堆。后来发现我太天真了。
比如说这个例子：

Example

1
[5,3,2,7,5,2]

如果按照上面的贪心办法，那么alex会选到:5,2(选择最前面的2),5 5+2+5=12
lee选到剩下的3,7,2 3+7+2=12
所以结果返回false.但是如果alex这么选：5, 2（选择排序最后的2）,7 5+2+7 =14. lee选择剩下的3,2,5 3+2+5=10
结果返回true。

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
bool stoneGame(vector<int>& piles) {
    int i, j, k;
    k = 0;
    i = 0, j = piles.size()-1;
    int sum_alex=0, sum_lee=0;
    while(k<piles.size()){
        int select;
        if(piles[i]>=piles[j]){
            select = piles[i];
            i++;
        }else{
            select = piles[j];
            j--;
        }
        if(k&1){ // lee
            sum_lee += select;
        }else{ // alex
            sum_alex+= select;
        }
        k++;
    }
    cout<<"sum_alex="<<sum_alex<<" sum_lee="<<sum_lee<<endl;
    if(sum_alex > sum_lee){
        return true;
    }
    return false;
}

想到的第二种解法：回溯. 悲催的是，超时了。

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
33
34
35
36
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int i, j, k, ans, best;
        k = 0;
        i = 0, j = piles.size()-1;
        ans = 0, best = 0;
        int sum = 0;
        for(auto pile:piles){
            sum+=pile;
        }
        dfs(ans, best, k, piles, i, j);
        if(best > sum - best){
            return true;
        }
        return false;
    }
    void dfs(int &ans,int &best, int k, vector<int>&piles, int i, int j){
        if(i==j){
            if(best < ans){
                best = ans;
            }
            return;
        }
        
        // 选择i
        ans += k%2==0?piles[i]:0;
        dfs(ans, best, k+1, piles, i+1, j);
        ans -= k%2==0?piles[i]:0;
        
        // 选择j
        ans += k%2==0?piles[j]:0;
        dfs(ans, best, k+1, piles, i, j-1);
        ans -= k%2==0?piles[j]:0;
    }
};

那么接下来，我能想到的唯一可能求解的方法就是动态规划的了，那么问题来了，状态转移方程怎么写呢？

暴力搜索

自顶向下

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
33
34
35
36
37
38
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        if(piles.size()==0){
            return false;
        }
        int sum = 0;
        for(int i=0;i<piles.size();i++){
            sum += piles[i];
        }
         vector<vector<int>> nums(piles.size(), vector<int>(piles.size(), -1));
        int stoneNum = getStones(piles, 0, piles.size()-1, nums);
        return stoneNum > (sum / 2);
    }
    int getStones(vector<int>& stones, int i, int j, vector<vector<int>>&nums){
        if(i <= j){
            if(nums[i][j]!=-1){
            return nums[i][j];
            }
            int sn1 = 0, sn2 = 0, sn = 0;
            // when there are even number of piles stones, it`s Alex`s turn
            if((j - i + 1) % 2 == 0){ 
                sn1 = nums[i+1][j] == -1 ? getStones(stones, i+1, j, nums) + stones[i] : nums[i+1][j] ;
                sn2 = nums[i][j-1] == -1 ? getStones(stones, i, j-1, nums) + stones[j] : nums[i][j-1] ; 
            }else{
                if(i < j){
                    sn1 = nums[i+1][j] == -1 ? getStones(stones, i+1, j, nums) : nums[i+1][j] ;                                 
                    sn2 = nums[i][j-1] == -1 ? getStones(stones, i, j-1, nums) : nums[i][j-1] ;       
                }
            }
            sn = sn1 > sn2 ? sn1 : sn2;
            nums[i][j] = sn;   
            return sn;
        }else{
            return 0;
        }
    }
};

时间复杂度：
当剩余可以选择的石头堆数为偶数时，说明此时轮到Alex选择．当Alex选择时，他可以从最左边也可以从最右边选择一堆石头，若他选择最左边的一堆，左边界i++，否则，右边界j–．

自底向上

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
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        if(piles.size()==0){
            return false;
        }
        int sum = 0;
        for(int i=0;i<piles.size();i++){
            sum += piles[i];
        }
        vector<vector<int>> nums(piles.size(), vector<int>(piles.size(), 0));
        for(int i=0;i<piles.size();i++){
            nums[i][i] = piles[i];
        }
        
        for(int k=1;k<piles.size()-1;k++){
            for(int i=0;i < nums.size() - k;i++){
                if(k % 2 == 0){
                    nums[i][i+k] = max(nums[i][i+k-1] + piles[i + k], nums[i+1][i+k] + piles[i]);
                }else{
                    nums[i][i+k] = max(nums[i][i+k-1], nums[i+1][i+k]);                    
                }
            }
        }
        return nums[0][nums.size()-1] <= (sum / 2);
    }
    
};

时间复杂度：O(n2) 空间复杂度：O(n2) 此时此题被转化成了Lee能够获得的最多的石头个数．
nums[i][j]表示的是当Lee只能在第i到第j堆石头之间选择时，他能够获得最大石头数量．
显然，nums[i][i]=piles[i]，也就是最后一次选择时，Lee只能选择第i堆石头．
当i < j时，当剩余可以选择的石头堆数为奇数时，即轮到Lee选择，此时，Lee有两种选择方法
nums[i][j] = max(nums[i][j-1] + piles[j] , nums[i+1][j] + piles[i])
Alex取胜的条件时，Lee能获得最多的石头数量仍然小于此时Alex能获得石头数量．

空间压缩

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
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        if(piles.size()==0){
            return false;
        }
        int sum = 0;
        for(int i=0;i<piles.size();i++){
            sum += piles[i];
        }
        vector<int> nums(piles.size(),0);
        for(int i=0;i<piles.size();i++){
            nums[i] = piles[i];
        }
        
        for(int k=1;k<piles.size()-1;k++){
            for(int i=nums.size()-k-1; i >= 0;i--){
                if(k % 2 == 0){
                    nums[i] = max(nums[i] + piles[i + k], nums[i+1] + piles[i]);
                }else{
                    nums[i] = max(nums[i], nums[i+1]);                    
                }
            }
        }
        return nums[0] <= (sum / 2);
    }
    
};

代码未能AC, 还需要考虑.