戳气球问题（状态转移优化版本）

题目描述：
给定一个长度为n的数组nums，表示n个气球上的数字。你的目标是戳破所有气球，获得最大得分。当你戳破第i个气球时，你可以获得nums[i-1] * nums[i] * nums[i+1]的分数（假设nums[-1] = nums[n] = 1）。求能够获得的最大得分。

解题过程：

1. 问题分析

• 戳破气球的顺序会影响最终得分
• 每次戳破气球时，得分取决于该气球和其左右相邻气球的数值
• 我们需要找到最优的戳破顺序，使得总得分最大化

2. 状态定义
   定义dp[i][j]表示戳破区间(i, j)内所有气球能获得的最大得分，其中区间为开区间，即i和j位置的气球不戳破。

3. 状态转移方程
   对于区间(i, j)，我们考虑最后戳破哪个气球k（i < k < j）：
   dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中k从i+1到j-1

4. 边界条件

• 当区间内没有气球时（即j = i + 1），dp[i][j] = 0
• 我们需要在原始数组前后各添加一个值为1的气球

5. 计算顺序
   按区间长度从小到大计算：

def maxCoins(nums):
    n = len(nums)
    # 在数组前后各添加一个1
    balloons = [1] + nums + [1]
    m = len(balloons)
    
    dp = [[0] * m for _ in range(m)]
    
    # 按区间长度从小到大计算
    for length in range(2, m):  # 区间长度至少为2
        for i in range(m - length):
            j = i + length
            # 枚举最后戳破的气球k
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j], 
                              dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j])
    
    return dp[0][m-1]

6. 状态转移优化
   原始方法的时间复杂度是O(n³)。我们可以通过以下优化技巧：

• 记忆化搜索减少重复计算
• 提前计算和缓存乘积结果
• 使用更紧凑的数据结构

优化后的实现：

def maxCoins_optimized(nums):
    n = len(nums)
    balloons = [1] + nums + [1]
    m = len(balloons)
    
    dp = [[0] * m for _ in range(m)]
    
    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            # 预计算基础值
            base = balloons[i] * balloons[j]
            # 优化：减少重复乘法计算
            for k in range(i + 1, j):
                current = dp[i][k] + dp[k][j] + base * balloons[k]
                if current > dp[i][j]:
                    dp[i][j] = current
    
    return dp[0][m-1]

7. 复杂度分析

• 时间复杂度：O(n³)，需要三层循环
• 空间复杂度：O(n²)，用于存储dp数组

这个问题的关键在于理解开区间的定义和最后戳破气球的思路，通过动态规划可以系统地找到最优解。