312.戳气球

链接：312.戳气球
难度：Hard
标签：数组、动态规划
简介：有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字，这些数字存在数组  nums  中。现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得  nums[left] _ nums[i] _ nums[right]  个硬币。  这里的  left  和  right  代表和  i  相邻的两个气球的序号。注意当你戳破了气球 i 后，气球  left  和气球  right  就变成了相邻的气球。,求所能获得硬币的最大数量。

题解 1 - python

• 编辑时间：2024-06-09
• 执行用时：3651ms
• 内存消耗：33MB
• 编程语言：python
• 解法介绍：dfs, 从下往上，刚开始没有气球，逐渐增加气球。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        @cache
        def dfs(l: int, r: int) -> int:
            return max((nums[m] * nums[l] * nums[r] + dfs(l, m) + dfs(m, r) for m in range(l + 1, r)), default = 0)
        return dfs(0, len(nums) - 1)

题解 2 - typescript

• 编辑时间：2020-07-25
• 执行用时：124ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：dp[i][j] = 在 i 到 j 中的最大值。dp[i][j] = dp[i]*dp[k]*dp[j] + dp[i][k] + dp[k][j],k 为遍历。

function maxCoins(nums: number[]): number {
  const len = nums.length;
  const val = [1, ...nums, 1];
  const dp = new Array(len + 2).fill(0).map(_ => new Array(len + 2).fill(-1));
  return solve(0, len + 1);
  function solve(left: number, right: number): number {
    if (left >= right - 1) return 0;
    if (dp[left][right] !== -1) return dp[left][right];
    for (let i = left + 1; i < right; i++) {
      let sum = val[left] * val[i] * val[right];
      sum += solve(left, i) + solve(i, right);
      dp[left][right] = Math.max(dp[left][right], sum);
    }
    return dp[left][right];
  }
}

题解 3 - typescript

• 编辑时间：2020-07-25
• 执行用时：104ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：根据题解 1 改为动态规划。

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