(C++/Python）LeetCode 312 戳气球_leetcode 312. 戳气球python

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

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

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

思路：
动态规划记忆法
具体参考：LeetCode 题解 戳气球动态规划问题

代码如下：
C++：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size()+2;
        nums.insert(nums.begin(),1);
        nums.insert(nums.end(),1);
        vector<vector<int>>dp(n,vector<int>(n,0));
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                // if(j-i<2){
                //     continue;
                // }
                for(int k=i+1;k<j;k++){
                    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
10
11
12
13
14
15
16
17
18
19
20

Python：

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n=len(nums)+2
        nums=[1]+nums+[1]
        dp=[[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if j-i>1:
                    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
10
11