312戳气球

向右看齐 2023-02-24 01:32 25阅读 0赞

## 一、前言 ##

分类：动态规划。

问题来源LeetCode 312 难度：困难。

问题链接：[https://leetcode-cn.com/problems/burst-balloons/][https_leetcode-cn.com_problems_burst-balloons]

## 二、题目 ##

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums\[left\] \* nums\[i\] \* nums\[right\] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。

**说明：**

*  你可以假设 nums\[-1\] = nums\[n\] = 1，但注意它们不是真实存在的所以并不能被戳破。
 *  0 ≤ n ≤ 500, 0 ≤ nums\[i\] ≤ 100

**示例：**

输入: [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

## 三、思路 ##

这道题不容易理解的是：怎样得到递推公式和怎样理解递推公式。

### 3.1 递推公式获得 ###

状态表示： f\[i\]\[j\] 表示戳破 （i，j）之间所有气球的集合（开区间），属性（最大值）。

状态计算：设 i 和 j 之间最后一个被戳破的气球为 k，那此时（i，k） 和（k，j） 之间的气球已被戳破，最后 （i，j） 之间只剩下气球 k，相邻的就是气球 i 和 j，j - i >= 2时，f\[i\]\[j\] = f\[i\]\[k\] + f\[k\]\[j\] + p\[i\]\*p\[k\]\*p\[j\]。

递推公式：f\[i\]\[j\] = f\[i\]\[k\] + f\[k\]\[j\] + p\[i\]\*p\[k\]\*p\[j\]

问题答案：f\[0\]\[n+1\]

### 3.2递推公式理解 ###

1.  先理解题意过程，戳破一个气球两边的气球就会想中间靠拢，成为相邻的气球。
2.  在区间（i，j） j - 2 >=2，中会有一个最后戳破的气球设为k，f\[i\]\[j\] = f\[i\]\[k\] + f\[k\]\[j\] + p\[i\]\*p\[k\]\*p\[j\]，这里最关键的是区间（i，j）是开区间，在计算f\[i\]\[j\]时，i 和 j 是不会被戳破的。

## 四、总结 ##

加深理解：递推公式获得和理解获得的过程。

## 五、编码实现 ##

//==========================================================================
    /*
    * @file    : 312_MaxCoins.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107193574
    * @author  : niebingyu
    * @date    : 2020/07/07
    * @title   : 戳气球
    * @purpose : 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。
    *            如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。
    *            注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
    *            求所能获得硬币的最大数量。
    
    * 说明:
    * 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
    * 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
    
    * 示例:
    * 输入: [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
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/burst-balloons/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_MAXCOINS namespace NAME_MAXCOINS {
    #define NAMESPACE_MAXCOINSEND }
    NAMESPACE_MAXCOINS
    
    // 动态规划
    // 递推公式：f[i][j] = f[i][k] + f[k][j] + p[i] * p[k] * p[j]
    class Solution 
    {
    public:
        int maxCoins(vector<int>& nums) 
    	{
            nums.insert(nums.begin(),1);
            nums.push_back(1);
    
            int n = nums.size();
            vector<vector<int>> dp(n, vector<int>(n,0));   //dp[i][j]表示第i至第j个元素这个区间能获得的最大硬币数
            int j = 0;
            for (int r = 2; r < n; r++)           
            {
                for (int i = 0; i < n - r; i++)    
                {
                    j = i + r;            
                    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];
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int expect)
    {
        Solution s;
        int result = s.maxCoins(nums);
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed." << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums = { 3,1,5,8 };
        int expect = 167;
        
        test("Test1()", nums, expect);
    }
    
    NAMESPACE_MAXCOINSEND
    // 测试 用例 END
    //
    
    void MaxCoins_Test()
    {
        NAME_MAXCOINS::Test1();
    }

**执行结果：**

![20200707234930973.png][]

[https_leetcode-cn.com_problems_burst-balloons]: https://leetcode-cn.com/problems/burst-balloons/
[20200707234930973.png]: /images/20230209/af1d2d4d25414559a242cdab9106762c.png