168. Burst Balloons

Burst Balloons,
区间型动态规划, 区间长度 len 从小到大循环, 2 to n; 然后循环起点 i, 0 to n - len.

子问题, 从最后出现结果的情况开始思考, 反推.
- 设f[i][j]为扎破i+1~j-1号气球，最多获得的金币数.
- i和j不能扎破
f[i][j] = max i<k<j {f[i][k] + f[k][j] + a[i] * a[k] * a[j]}, k 是 i..j 中间某个气球.

方程: f[i][j] = max(f[i][j], f[i][mid] + f[mid][j] + A[i] * A[mid] * A[j])

初始条件：f[0][1] = f[1][2] = …= f[N][N+1] = 0
– 当没有气球要扎破时，最多获得0枚金币

计算顺序: 按照区间长度 len or (j-i) 从小到大的顺序去算.
– f[0][1], f[1][2], f[2][3], …, f[N][N+1]
– f[0][2], f[1][3], f[2][4], …, f[N-1][N+1]
–…
– f[0][N+1]

时间复杂度O(n^3)，空间复杂度O(n^2)

class Solution:
    """
    @param nums: A list of integer
    @return: An integer, maximum coins
    """
    def maxCoins(self, nums):
        # init
        A = [1] + nums + [1]
        # print(A)
        n = len(A)
        f = [[-float("inf")] * n for _  in range(n)]
        # print(f)

        for i in range(n - 1):
            f[i][i + 1] = 0

        for size in range(2, n):
            for i in range(n - size):
                j = i + size
                for mid in range(i + 1, j):
                    f[i][j] = max(f[i][j], f[i][mid] + f[mid][j] + A[i] * A[mid] * A[j])
        return f[0][n - 1]

nums = [4, 1, 5, 10]
# Output：270