1140.js

/** ------------------------------------------------------------------------------
 * 
 * 1140. Stone Game 2
 * Topics: DP
 * https://leetcode.com/problems/stone-game-ii/
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} piles
 * @return {number}
 */
var stoneGameII = function (piles) {
  const n = piles.length

  const dp = new Array(n + 1).fill(0)

  for (let i = n - 1; i >= 0; i--) {
    dp[i] = dp[i + 1] + piles[i]
  }

  const memo = Array.from({ length: n }, () => new Array(n + 1).fill(0))

  const maxStonesAliceCanGet = (m, currentPile) => {
    if (currentPile >= n) return 0

    if (currentPile + 2 * m >= n) {
      return dp[currentPile]
    }

    if (memo[currentPile][m] !== 0) return memo[currentPile][m]

    let maxStones = 0

    for (let x = 1; x <= 2 * m; x++) {
      const currentStones = dp[currentPile] - maxStonesAliceCanGet(Math.max(m, x), currentPile + x)
      maxStones = Math.max(maxStones, currentStones)
    }

    memo[currentPile][m] = maxStones
    return maxStones
  }

  return maxStonesAliceCanGet(1, 0)
}

console.log(stoneGameII([2, 7, 9, 4, 4]))