力扣312题：戳气球_力扣戳气球

力扣312题：戳气球

题目描述

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

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

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

输入输出样例

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

1
2
3
4
5
6

输入：nums = [1,5]
输出：10
1
2

解法，动态规划

int maxCoins(vector<int>&nums)
    {
        //使用动态规划的思想，从底向上进行实现

        //首先创建头尾都为1的辅助数组，方便结果的计算
        int length=nums.size();

        vector<int>tempArr(length+2,1);
        //创建二维动态规划数组
        vector<vector<int>>dp(length+2,vector<int>(length+2,0));

        //初始化辅助数组，将num的值拷贝到对应的tempArr中去
        for(int i=1;i<=length;i++)
        {
            tempArr[i]=nums[i-1];
        }

        //建立状态转移方程
        //设置初始区间为3,表示开区间的长度，对每一个区间长度进行循环
        for(int len=3;len<=length+2;len++)
        {
            //i表示区间的左端点
            for(int i=0;i<=length+2-len;i++)
            {
                int res=0;
                //k表示开区间内的索引（代表区间最后一个被戳破的气球），i+len-1,表示区间的右端点
                for(int k=i+1;k<i+len-1;k++)
                {
                    //left,right分别代表左区间和右区间
                    int left=dp[i][k];
                    int right=dp[k][i+len-1];
                    int tempSum=tempArr[k]*tempArr[i]*tempArr[i+len-1];
                    int sum=left+right+tempSum;
                    //逐个取金币的最大值
                    dp[i][i+len-1]=max(dp[i][i+len-1],sum);
                    
                }
            }
        }
        return dp[0][length+1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41