好的，我们来详细讲解一下 LeetCode 上的 312 题 “Burst Balloons”。

题目描述

给定一个整数数组 nums，其中 nums[i] 表示第 i 个气球的分数。如果你戳破气球 i，你可以获得 nums[left] nums[i] nums[right] 分数。这里的 left 和 right 是 i 的相邻索引。当气球被戳破后，其左右相邻的气球会成为新的相邻气球。

求戳破所有气球所能获得的最大分数。

示例

输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167

解题思路

这个问题可以通过动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示戳破从第 i 个到第 j 个气球所能获得的最大分数。

动态规划转移方程

1. 初始化：
   • dp[i][i] = nums[i-1] * nums[i] * nums[i+1]，因为戳破单个气球时，左右相邻的气球分别是 nums[i-1] 和 nums[i+1]。
2. 状态转移：
   • 对于每一个子数组 nums[i...j]，我们考虑最后一个被戳破的气球 k（i <= k <= j）。
   • 戳破 k 后，左边部分的最大分数是 dp[i][k-1]，右边部分的最大分数是 dp[k+1][j]。
   • 戳破 k 本身获得的分数是 nums[i-1] * nums[k] * nums[j+1]。
   • 因此，dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j])。

边界处理

为了方便处理边界情况，我们可以在 nums 数组的两端各添加一个 1，这样就不需要特别处理边界情况。

代码实现

def maxCoins(nums):

nums = [1] + nums + [1]
n = len(nums)

# 初始化dp数组
dp = [[0] * n for _ in range(n)]

# 填充dp数组
for length in range(2, n):
    for i in range(1, n-length+1):
        j = i + length - 1
        for k in range(i, j):
            # 计算戳破k气球的最大分数
            dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1] * nums[k] * nums[j] + dp[k+1][j])

# 最终结果
return dp[1][n-1]

print(maxCoins([3,1,5,8])) # 输出: 167

解释

1. 初始化：
   • nums 变为 [1, 3, 1, 5, 8, 1]。
   • dp 是一个 6x6 的二维数组，初始值为0。
2. 填充dp数组：
   • 外层循环 length 从2到5（表示子数组的长度）。
   • 中层循环 i 从1到 n-length（表示子数组的起始位置）。
   • 内层循环 k 从 i 到 j-1（表示最后一个被戳破的气球的位置）。
3. 计算最大分数：
   • 通过状态转移方程更新 dp[i][j]。

最终，dp[1][n-1] 就是戳破所有气球所能获得的最大分数。

希望这个详细的解释和代码实现能帮助你理解并解决这个题目！如果有任何进一步的问题，欢迎继续提问。