2021-10-25-戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

https://leetcode-cn.com/problems/burst-balloons/

反转过程, 从添加气球开始

import functools


def f(nums):
    n = len(nums)
    val = [1] + nums + [1]
    def f1(left, right):
        if left >= right - 1:
            return 0

        best = 0
        for i in range(left+1, right):
            total = val[left] * val[i] * val[right]
            total += f1(left, i) + f1(i, right)
            best = max(best, total)

        return best

    return f1(0, n + 1)