1140

1140. Stone Game II (Medium)

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:

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

Related Topics:
Dynamic Programming

Solution 1. DP

Let dp[i][m] be optimal result Alex can get on subarray A[i..(N-1)] and with inital M = m. It's a pair<int, int> where the first element is the stones Alex can get and the second is the stones Lee can get.

dp[i][m] = <p.second + A[i] + ... + A[i + x - 1], p.first>
           where p = dp[i + x][max(m, x)], 1 <= x <= 2m

The answer is dp[0][1].first.

// OJ: https://leetcode.com/problems/stone-game-ii/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    pair<int, int> dp[101][101] = {};
    int presum[101] = {};
    pair<int, int> dfs(vector<int> &A, int i, int M) {
        if (i == A.size()) return {0, 0};
        if (dp[i][M].first != 0) return dp[i][M];
        for (int x = 1; x <= min((int)A.size() - i, 2 * M); ++x) {
            auto p = dfs(A, i + x, max(M, x));
            int sum = presum[i + x] - presum[i];
            if (p.second + sum > dp[i][M].first) dp[i][M] = { p.second + sum, p.first };
        }
        return dp[i][M];
    }
public:
    int stoneGameII(vector<int>& A) {
        partial_sum(begin(A), end(A), presum + 1);
        return dfs(A, 0, 1).first;
    }
};

Solution 2. DP

// OJ: https://leetcode.com/problems/stone-game-ii/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    int dp[101][101] = {}, sum[101] = {};
    int dfs(vector<int> &A, int i, int M) {
        if (i == A.size()) return 0;
        if (dp[i][M]) return dp[i][M];
        for (int X = 1; X <= 2 * M && i + X <= A.size(); ++X) dp[i][M] = max(dp[i][M], sum[A.size()] - sum[i] - dfs(A, i + X, max(M, X)));
        return dp[i][M];
    }
public:
    int stoneGameII(vector<int>& A) {
        partial_sum(begin(A), end(A), sum + 1);
        return dfs(A, 0, 1);
    }
};