leetcode 1140

问题

Alex and Lee 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.

Alex and Lee take turns, with Alex 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 Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

1
2
3
Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

分析

思路: 使用动态规划，$f(i,j)$ 表示当从下标为 $i$ 的石块开始取，且 $m = j$ 时，先取的人能够获得的最大石块数。则有
$$
f(i,j) = sum(A[i]+..A[i+k-1]) + suffixSum(i+k) - f(i+k, min(max(k, m), n));
$$
限制 $m$ 的最大值为 $n$，（n/2 + 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
// 自顶向下
class Solution {
public:
    vector<int> suffixSum;
    vector<vector<int>> memo;
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        suffixSum = vector<int>(n+1, 0);
        memo = vector<vector<int>>(n, vector<int>(n+1, 0));
        suffixSum[n] = 0;
        for (int i = n-1; i >= 0; --i) {
            suffixSum[i] = suffixSum[i+1]+piles[i];
        }
        return dp(0, 1, piles);
    }
    int dp(int i, int m, vector<int>& piles) {
        int n = piles.size();
        if (i >= n) return 0;
        if (2*m >n-i) return suffixSum[i];
        if (memo[i][m] != 0)
            return memo[i][m];
        int ans = 0;
        int sum = 0;
        int limit = min(2*m, n-i);
        for (int k = 1; k <= limit; ++k) {
            sum += piles[i+k-1];
            ans = max(ans, sum + (suffixSum[i+k] - dp(i+k, min(n/2+1, max(m, k)), piles)));
        }
        return memo[i][m] = ans;
    }
};