HackMD
1140.Stone Game II
tags: Medium,Array,Math,DP
題目描述
Alice and Bob continue their games with piles of stones. There are a 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.
Alice and Bob take turns, with Alice starting first. Initially, M = 1.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.
範例
Example 1:
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
Example 2:
Input: piles = [1,2,3,4,5,100]
Output: 104
Constraints:
- 1 <=
piles.length<= 100 - 1 <=
piles[i]<= 104
解答
C++
class Solution {
public:
int stoneGameII(vector<int>& piles) {
ios_base::sync_with_stdio(0), cin.tie(0);
int n = piles.size();
if (n == 1) {
return piles[0];
} else if (n == 2) {
return piles[0] + piles[1];
}
vector<int> suffixSum(n, 0);
suffixSum[n - 1] = piles[n - 1];
for (int i = n - 2; i >= 0; i --) {
suffixSum[i] = suffixSum[i + 1] + piles[i];
}
vector<vector<int>> dp(n, vector(n, 0));
play(piles, dp, suffixSum, 0, 1);
return dp[0][1];
}
int play(vector<int>& piles, vector<vector<int>>& dp, vector<int>& suffixSum, int start, int M) {
if (start == piles.size()) {
return 0;
}
if (2 * M >= piles.size() - start) {
return suffixSum[start];
}
if (dp[start][M]) {
return dp[start][M];
}
int opponentScore = numeric_limits<int>::max();
for (int m = 1; m <= 2 * M; m ++) {
opponentScore = min(opponentScore, play(piles, dp, suffixSum, start + m, max(m, M)));
}
dp[start][M] = suffixSum[start] - opponentScore;
return dp[start][M];
}
};
Jerry WuFri, 23 May, 2023
