1140.石子游戏-ii.md

1140.石子游戏-ii

/*
 * @lc app=leetcode.cn id=1140 lang=typescript
 *
 * [1140] 石子游戏 II
 */

// @lc code=start
function stoneGameII(piles: number[]): number {}
// @lc code=end

解法 1: dfs

function stoneGameII(piles: number[]): number {
  const n = piles.length
  const sums: number[] = []
  for (let i = n - 1; i >= 0; i--) {
    sums[i] = (sums[i + 1] ?? 0) + piles[i]
  }
  const cache = [Array.from({ length: n }, () => new Array(n)), Array.from({ length: n }, () => new Array(n))]
  const dfs = (index: number, m: number, player: number): number => {
    if (index >= n) return 0
    if (cache[player][index][m] !== undefined) return cache[player][index][m]
    let res = 0
    for (let i = index; i < Math.min(n, 2 * m + index); i++) {
      res = Math.max(res, sums[index] - dfs(i + 1, Math.max(m, i - index + 1), player ^ 1))
    }
    cache[player][index][m] = res
    return res
  }
  return dfs(0, 1, 0)
}

Case

test.each([
  { input: { piles: [2, 7, 9, 4, 4] }, output: 10 },
  { input: { piles: [1, 2, 3, 4, 5, 100] }, output: 104 },
])('input: piles = $input.piles', ({ input: { piles }, output }) => {
  expect(stoneGameII(piles)).toEqual(output)
})