312.戳气球

戳气球

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字。戳破第 i 个气球可以获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币。求所能获得硬币的最大数量。

解析

区间 DP：dp[i][j] 表示戳破开区间 (i,j) 内所有气球能获得的最大硬币数。

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