Stone Game II

Description

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(javascript)

/*
 * @lc app=leetcode id=1140 lang=javascript
 *
 * [1140] Stone Game II
 */


// @lc code=start
/**
 * @param {number[]} piles
 * @return {number}
 */
const stoneGameII = function (piles) {
  const memo = {}
  const alice = (index, m) => {
    memo[index] = memo[index] || {}
    if (memo[index][m] !== undefined) {
      return memo[index][m]
    }
    if (index > piles.length - 1) {
      return 0
    }
    const count = 2 * m
    let max = 0
    let sum = 0
    const lee = (index2, m) => {
      let min = Infinity
      const count2 = 2 * m
      for (let i = index2; (i < index2 + count2) && (i < piles.length); i++) {
        const nextM = Math.max(i - index2 + 1, m)
        min = Math.min(
          min,
          alice(i + 1, nextM),
        )
      }
      return min === Infinity ? 0 : min
    }
    for (let i = index; (i < index + count) && (i < piles.length); i++) {
      sum += piles[i]
      const nextM = Math.max(i - index + 1, m)
      max = Math.max(
        max,
        sum + lee(i + 1, nextM),
      )
    }
    memo[index][m] = max
    return memo[index][m]
  }
  return alice(0, 1)
}
// @lc code=end