动态规划：力扣312. 戳气球_戳气球力扣

1、题目描述：

2、题解：

动态规划：

1、状态定义；

2、状态转移方程；

3、初始化；base case

4、输出；

5、思考状态压缩。

可以用递归去求，但是会存在重叠子问题，加个备忘录可以解决重复问题。或者用DP table
由题意nums[-1] = nums[n] = 1，我们先把nums数组扩展，在其前后分别加上1，此时数组的长度比原数组的长度多2.
状态定义：
dp[i][j],表示开区间（i,j)之间coin的数量
状态转移方程：

dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
其中k表示最后一个戳破的气球，dp[i][k]是开区间(i,k)之间的coin值，dp[k][j]为开区间(k,j)之间的coin值。
那得先把开区间 (i, k) 的气球都戳破，再把开区间 (k, j) 的气球都戳破；前面的两个的结果与剩下的K没有关系，最后剩下的气球 k，相邻的就是气球 i 和气球 j，
这时候戳破 k 的话得到的分数就是 nums[i]*nums[k]*nums[j]

对于一组给定的 i 和 j，我们只要穷举 i < k < j 的所有气球 k，选择得分最高的作为 dp[i][j] 的值即可
#最后戳破的气球是哪个？
for k in [i+1,j):
    #择优做选择，使得 dp[i][j] 最大
    dp[i][j] = Math.max(
        dp[i][j], 
        dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
1
2
3
4
5
6
7
8
9
10
11

base case:
dp数组的值都为0
处理技巧：

我们需要求的是dp[0][n - 1],n 为新数组的长度。
从下往上遍历 从左到右遍历，可保证对于任一 dp[i][j]，所有 dp[i][k] 和 dp[k][j] 已经被计算。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * (n) for _ in range(n)]
        for i in range(n - 2,-1,-1):
            for j in range(i + 1,n):
                for  k in range(i+1,j):
                    dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
        return dp[0][n-1]
1
2
3
4
5
6
7
8
9