[LeetCode]Burst Balloons 爆气球

声明：原题目转载自LeetCode，解答部分为原创

Problem：

       Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 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

Solution：

        思路：比较复杂的题目，题意简单的理解是“刺破一个气球就获得其与两个相邻气球的数字乘积的硬币，求所能获得的最大货币数”，即找出能够使获得的货币数最多的刺破顺序。最初的想法是穷举每一种可能，时间复杂度为O（n^3），光荣地获得了一个“Time Limit”，由于多次微调也无法大幅度减少事件复杂度，最终参考了下他人思路，发现大神们给出的是“动态规划 + 分而治之”的解题思路。思路不易，独自实现超难，实际代码很少。最难理解的是对“dp”二维数组的处理，有三重循环。第一重循环是确定每个阶段所截取的每组气球的个数，第二重循环是确定分组，获得每组气球的起始下标，第三重循环是选择刺破的气球下标

        代码如下：

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.push_back(1);
        nums.insert(nums.begin(), 1);
        
        int later_size = nums.size();
        int ori_size = later_size - 2;
        
        vector<vector<int> > dp(later_size, vector<int>(later_size, 0));
        for(int length = 1; length <= ori_size; length ++)
        {
        	for(int head = 1; head <= ori_size - length + 1 ; head ++)
        	{
        		int tail = head + length - 1;
        		for(int point = head ; point <= tail ; point ++ )
        		{
        			int ori_coins = dp[head][tail];
        			int later_coins = dp[head][point - 1] + dp[point + 1][tail] + nums[head - 1] * nums[point] * nums[tail + 1];
        			dp[head][tail] = max(ori_coins, later_coins);
        			
        			//注释部分功能：输出单步计算结果 
/*        			for(int i = 0 ; i < dp.size() ; i ++)
					{
						for(int j = 0 ; j < dp[0].size() ; j ++)
						{
							cout << dp[i][j] << "\t";
						}
						cout << endl;
					}
					getchar();
*/ 
				}
			}	
		}

		//恢复原数组，删除插入的头尾两个数据		
		nums.erase(nums.begin());
		nums.erase(nums.end() - 1);
		
		return dp[1][ori_size];
    }
};

int main()
{
	Solution text;
	Solution text_;
	vector<int> array;
	array.push_back(3);
	array.push_back(1);
	array.push_back(5);
	array.push_back(8);
	cout << text.maxCoins(array) << endl;
	cout << text_.maxCoins(array) << endl;
	return 0;	
	return 0;
}