1140. Stone Game II.md

1140. Stone Game II

---

Difficulty : Medium

Related Topics : Dynamic Programming

---

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

---

Solution

• mine
  • Java
    • DFS & Memorize Runtime: 1 ms, faster than 74.92%, Memory Usage: 39.5 MB, less than 13.21% of Java online submissions

      // O(N^2)time
      // O(N^2)space
      public int stoneGameII(int[] piles) {
          int n = piles.length;
          int[] preSum = new int[n + 1];
          for(int i = 0; i < n; i++){
              preSum[i + 1] = preSum[i] + piles[i];
          }
          // a + b = preSum[n];
          // a - b = dx
          // a = (preSum[n] + dx) / 2
          int dx = dfs(preSum, 0, n, 1, new int[n + 1][n + 1]);
          return (preSum[n] + dx) / 2;
      }
      
      
      int dfs(int[] preSum, int l, int r, int m, int[][] memo){
          if(l >= r) return 0;
          if(l + 2 * m >= r) return preSum[r] - preSum[l];
          if(memo[l][m] != 0) return memo[l][m];
          int res = Integer.MIN_VALUE;
          for(int i = 1; i <= 2 * m; i++){
              int sum = preSum[l + i] - preSum[l];
              res = Math.max(res, sum - dfs(preSum, l + i, r, Math.max(i, m), memo));
          }
          memo[l][m] = res;
          return res;
      }
      

---