Leetcode 877. 石子游戏

题目

Leetcode 877. 石子游戏

代码（9.23 首刷看解析）

博弈

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int len = piles.size();
        vector<vector<int>> dp(len, vector<int>(len));
        for(int i = 0; i < len; i++)    
            dp[i][i] = piles[i];
        for(int i = len-2; i >= 0; i--) {
            for(int j = i+1; j < len; j++) {
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
            }
        }
        return dp[0][len-1] > 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码（10.8 二刷看解析）

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for(int i = 0; i < n; i++)
            dp[i][i] = i;
        for(int i = n-2; i >= 0; i--) {
            for(int j = i+1; j < n; j++) {
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15