力扣 312. 戳气球

解法：dfs

def maxCoins(nums):
    @lru_cache(None)
    def solve(left, right):
        if left >= right - 1:
            return 0
        best = 0
        for i in range(left + 1, right):
            cur = new[left] * new[i] * new[right]
            cur += solve(left, i) + solve(i, right)
            best = max(best, cur)
        return best
    new = [1] + nums + [1]
    return solve(0, len(nums) + 1)

解法二：动态规划

def maxCoins(nums):
    # 动态规划
    n = len(nums)
    dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
    new = [1] + nums + [1]
    for i in range(n - 1, -1, -1):      # 左边缘气球
        for j in range(i + 2, n + 2):   # 右边缘气球
            for k in range(i + 1, j):   # 戳爆的气球
                total = new[i] * new[k] * new[j]
                total += dp[i][k] + dp[k][j]
                dp[i][j] = max(dp[i][j], total)
    return dp[0][n + 1]