312.戳气球.md

312.戳气球

/*
 * @lc app=leetcode.cn id=312 lang=typescript
 *
 * [312] 戳气球
 */

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

解法 1: 回溯

function maxCoins(nums: number[]): number {
  let res = 0
  const dfs = (nums: number[], sum = 0) => {
    if (!nums.length) {
      res = Math.max(res, sum)
      return
    }

    for (let i = 0; i < nums.length; i++) {
      const tmp = nums[i] * (nums[i - 1] ?? 1) * (nums[i + 1] ?? 1)

      dfs([...nums.slice(0, i), ...nums.slice(i + 1)], sum + tmp)
    }
  }
  dfs(nums)
  return res
}

解法 2: 分治

function maxCoins(nums: number[]): number {
  nums = [1, ...nums, 1]

  const cache: number[][] = new Array(nums.length).fill(0).map(() => [])

  const dfs = (i = 0, j = nums.length - 1): number => {
    if (cache[i][j]) return cache[i][j]
    if (j - i === 2) return nums[i] * nums[i + 1] * nums[j]
    if (j - i < 2) return 0

    let max = 0
    for (let k = i + 1; k < j; k++) {
      max = Math.max(max, dfs(i, k) + dfs(k, j) + nums[i] * nums[k] * nums[j])
    }
    cache[i][j] = max
    return max
  }

  return dfs()
}

解法 3: 动态规划

function maxCoins(nums: number[]): number {
  nums = [1, ...nums, 1]
  const n = nums.length
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
  for (let i = n - 2; i >= 0; i--) {
    for (let j = i + 2; j < n; j++) {
      for (let k = i + 1; k < j; k++) {
        const cur = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
        dp[i][j] = Math.max(dp[i][j], cur)
      }
    }
  }

  return dp[0][n - 1]
}

Case

test.each([
  { input: { nums: [3, 1, 5, 8] }, output: 167 },
  { input: { nums: [1, 5] }, output: 10 },
  { input: { nums: [7, 9, 8, 0, 7, 1, 3, 5, 5, 2, 3] }, output: 1654 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(maxCoins(nums)).toEqual(output)
})