312. 戳气球

Difficulty

Hard

法1 动态规划第二类区间型

思路

首先在nums数组一前一后都加[1]，可以防止越界。

定义状态dp[i][j] 表示戳破nums[i-1:j]之间所有气球的最大分数。谨记：是不包括i 和 j 的。

所以dp[i][i+1] = 0 因为之间没有气球，直接为0

假设k是最后一个戳破的气球，那么dp[i][j]=nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j]

然后k作为最后戳破的气球，k有 j - i - 1 种选择。遍历所有的选择，然后选结果最大的。

整个过程就相当于在填充如下的dp数组：

题解


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # 先在左右两边做一个扩充
        nums = [1] + nums + [1]
        
        # 默认为 0
        dp = [[0] * len(nums) for _ in nums]

        for i in range(len(nums)-2, -1, -1):
            for j in range(i+2, len(nums), 1):
                # i, j 之间的所有戳法, 假设k是最后戳破的，所以k不能包含 i,j 本身
                for k in range(i+1, j, 1):
                    dp[i][j] = max(dp[i][j], 
                                    nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])

        return dp[0][-1]

矩阵相乘问题

教你一文破解连续区间分割问题：手撕矩阵链乘法与戳气球难题_黄波波19的博客-CSDN博客

初始化

对dp table初始化，𝒊 = 𝒋 时，矩阵链只有一个矩阵，乘法次数为0。由于是求最小值问题，其余先初始化为inf。

确定计算顺序

由dp table可看出，最终的解依赖子问题的最优解，因此计算顺序是自底向上计算。最终的最优解是dp[0][n]，就是右上角位置。对于这种问题，又可以分为两个方法来计算。 #但这两种方法时间复杂度都是O(n^3)

(1)：斜线遍历计算 (2)：从下到上从左到右遍历计算


输入：nums = [2, 3, 7, 9, 5, 2, 4, 8, 10, 12, 6, 5]
描述：有11个矩阵，矩阵大小分别为 2*3, 3*7, 7*9,.... 12*6, 6*5 
问题：这11个矩阵相乘，可得到的最小两数相乘的次数是多少。
	输出：954


class Solution2: # 时间复杂度O(n^3)
    def MatrixChainMultiply(self, p, n):
        D = [[float('inf')]*(n) for _ in range(n)]
        rec = [[0]*(n) for _ in range(n)]
        for i in range(n):
            D[i][i] = 0
        # 动态规划，下上->左右遍历！
        for i in range(n-2, -1,-1):  # i从下到上遍历，倒数第二行开始
            for j in range(i, n):    # j从左到右遍历
                # print(i,j)
                for k in range(i, j):  # 枚举所有分割位置
                    # 计算最少乘法次数
                    q = D[i][k] + D[k + 1][j] + p[i - 1] * p[k] * p[j]
                    D[i][j] = min(D[i][j], q)

        return D[0][n-1], D

if __name__ == "__main__":
    p = [2, 3, 7, 9, 5, 2, 4, 8, 10, 12, 6, 5]
    n = len(p) - 1

    count, D = Solution2().MatrixChainMultiply(p, n)
    print("--------无决策记录+下上->左右遍历--------")
    print("最少计算次数：", count)
    # for i in D:
    #     print(i)

最优方案追踪

下面这种方法是输出具体是如何增加进行加括号的方法：

增加一个二维数组来记录每个区间具体的 k 值


# 矩阵链乘法问题
class Solution: # 时间复杂度O(n^3)
    def MatrixChainMultiply(self, p, n):
        D = [[float('inf')]*(n) for _ in range(n)]
        rec = [[0]*(n) for _ in range(n)]
        for i in range(n):
            D[i][i] = 0
        # 动态规划
        for l in range(2, n+1):  # 区间长度从小到大
            # 以此计算子问题
            for i in range(0, n-l+1):
                j = i + l - 1
                # print(i,j)
                for k in range(i, j):  # 枚举所有分割位置
                    # 计算最少乘法次数
                    q = D[i][k] + D[k+1][j] + p[i-1]*p[k]*p[j]
                    if q < D[i][j]:
                        D[i][j] = q
                        rec[i][j] = k  # 记录最优决策
        return D[0][n-1], rec, D

# 最优方案追踪
# 输入矩阵链U1_6,追踪数组rec,位置索引i,j
# 输出矩阵链的加括号方式
def printMatrixChain(U, rec, i, j):
    if i == j:
        print(U[i], end='')
        return
    print("(", end='')
    printMatrixChain(U, rec, i, rec[i][j])
    print(")(", end='')
    printMatrixChain(U, rec, rec[i][j] + 1, j)
    print(")", end='')
    return

if __name__ == "__main__":
    p = [2, 3, 7, 9, 5, 2, 4, 8, 10, 12, 6, 5]
    n = len(p) - 1

    count, rec, D = Solution().MatrixChainMultiply(p, n)
    print("最少计算次数：", count)
    # for i in D:
    #    print(i)

    print("--------最优方案--------")
    U = '1234567890a'  # 每个字符相当于一个矩阵
    i, j = 0, n - 1
    printMatrixChain(U, rec, i, j)
    print()

312. 戳气球

法1 动态规划 第二类区间型

矩阵相乘问题

法1 动态规划第二类区间型