89戳气球(312)

作者: Turbo时间限制: 1S章节: 动态规划

晚于: 2020-09-02 12:00:00后提交分数乘系数50%

截止日期: 2020-09-09 12:00:00

问题描述 :

有 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 ≤ 300, 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

输入说明 :

首先输入气球数(即nums数组长度) n

然后输入n个整数，表示气球上的数字nums[i]

0 ≤ n ≤ 300, 0 ≤ nums[i] ≤ 100

输出说明 :

输出一个整数

输入范例 :

4 3 1 5 8

输出范例 :

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int maxCoins(vector<int>& nums) 
    {
        int n=nums.size();
        vector<vector<int>> dp(n+2,vector<int>(n+2,0));
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        for(int i=n-1;i>=0;i--)//倒着推，控制左边界
        {
            for(int j=i+2;j<=n+1;j++)//控制右边界
            {
                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];
    }
};
int main()
{
    int n,data;
    vector<int> nums;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>data;
        nums.push_back(data);
    }
    int res=Solution().maxCoins(nums);
    cout<<res<<endl;
    return 0;
}
/*
dp[i][j] 表示的是开区间 (i, j) 内戳破所有气球后，能获得的最大***数
相应的存在的与子问题的递推关系，用包含于 (i, j) 的一个索引 k 表示区间内被戳破的最后一个气球，
就能发现 dp[i][j] 的值就是戳破 k 右边的所有气球得到的*** dp[i][k] 加上戳破 k 左边的所有气球得到的*** dp[k][j] ，
再加上戳破索引 k 对应的气球得到的*** nums[i] * nums[k ] * nums[j]（这里注意中间的气球已经都被戳破了）
为什么大部分题解是倒序递推？ 这个现象常常出现在动态规划题里，很多都会用到倒推，
特别是用dp[i][j] 表示的某个区间的时候。。。
答案就是：动态规划在求解子问题一定要在父问题之前，假设这里父问题是求解 dp[2][8]，
对应的子问题有“求解 dp[5][8]”，如果这里外层索引循环用顺序，会发现，求解 dp[2][8] 会在求解 dp[5][8] 之前进行。
。。显然就不符合动态规划的规则了。当然也可以顺序，比如外层循环不是数组的一级索引，而是区间长度。。。
这样子是可以顺序的。

*/