leetcode 312. Burst Balloons

淡淡的烟草味﹌ 2022-08-20 02:29 216阅读 0赞

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

#include "stdafx.h"
    #include<vector>  
    #include<set>   
    #include<algorithm>  
    #include<iostream>  
    using namespace std;
    
    class Solution {
    public:
    	int do_once(set<pair<vector<int>, int>>&curnums)
    	{
    		vector<int>re;
    		set<pair<vector<int>, int>>newnums;
    		for (set<pair<vector<int>, int>>::iterator it = curnums.begin();
    			it != curnums.end(); it++)
    		{
    			if (it->first.size() == 2)
    			{
    				int t1 = it->second + (it->first[0] + 1)* it->first[1];
    				int t2 = it->second + (it->first[1] + 1)* it->first[0];
    				if (t1 > t2)
    					t2 = t1;
    				re.push_back(t2);
    			}
    			else
    			{
    				for (int j = 0; j < it->first.size(); j++)
    				{
    					vector<int>aa = it->first;
    					int sum = it->second;
    					if (j == 0)
    						sum += aa[0] * aa[1];
    					else if (j == it->first.size() - 1)
    						sum += aa[j - 2] * aa[j - 1];
    					else
    						sum += aa[j - 1] * aa[j] * aa[j + 1];
    					aa.erase(aa.begin() + j, aa.begin() + j + 1);
    					newnums.insert(pair<vector<int>, int>(aa, sum));
    				}
    			}
    		}
    		if (re.empty())
    		{
    			curnums = newnums;
    			return -1;
    		}
    		else
    		{
    			int max = 0;
    			for (int i = 0; i < re.size(); i++)
    				if (re[i]>max)
    					max = re[i];
    			return max;
    		}
    	}
    	int maxCoins(vector<int>& nums) {
    		if (nums.empty())
    			return 0;
    		if (nums.size() == 1)
    			return nums[0];
    		set<pair<vector<int>, int>>curnums;
    		curnums.insert(pair<vector<int>, int>(nums, 0));
    		int k = -1;
    		k = do_once(curnums);
    		while (k < 0)
    		{
    			k = do_once(curnums);
    		}
    		return k;
    	}
    };
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	
    	int aa[11] = { 7, 9, 8, 0, 7, 1, 3, 5, 5, 2, 3 };
    	vector<int>nums(aa,aa+11);
    	cout << sl.maxCoins(nums);
    
    	system("pause");
    	return 0;
    }

这个是最简单的想法，但很糟糕

改进一下，set换用map，性能提升不少，仍超时，譬如这个int aa\[15\] = \{ 2, 4, 8, 4, 0, 7, 8, 9, 1, 2, 4, 7, 1, 7, 3 \};

#include "stdafx.h"
    #include<vector>  
    #include<map>   
    #include<algorithm>  
    #include<iostream>  
    using namespace std;
    
    class Solution {
    public:
    	int do_once(map<vector<int>, int>&curnums)
    	{
    		vector<int>re;
    		map<vector<int>, int>newnums;
    		for (map<vector<int>, int>::iterator it = curnums.begin();
    			it != curnums.end(); it++)
    		{
    			if (it->first.size() == 2)
    			{
    				int t1 = it->second + (it->first[0] + 1)* it->first[1];
    				int t2 = it->second + (it->first[1] + 1)* it->first[0];
    				if (t1 > t2)
    					t2 = t1;
    				re.push_back(t2);
    			}
    			else
    			{
    				for (int j = 0; j < it->first.size(); j++)
    				{
    					vector<int>aa = it->first;
    					int sum = it->second;
    					if (j == 0)
    						sum += aa[0] * aa[1];
    					else if (j == it->first.size() - 1)
    						sum += aa[j - 2] * aa[j - 1];
    					else
    						sum += aa[j - 1] * aa[j] * aa[j + 1];
    					aa.erase(aa.begin() + j, aa.begin() + j + 1);
    					newnums[aa] = sum>newnums[aa] ? sum : newnums[aa];
    				}
    			}
    		}
    		if (re.empty())
    		{
    			curnums = newnums;
    			return -1;
    		}
    		else
    		{
    			int max = 0;
    			for (int i = 0; i < re.size(); i++)
    				if (re[i]>max)
    					max = re[i];
    			return max;
    		}
    	}
    	int maxCoins(vector<int>& nums) {
    		if (nums.empty())
    			return 0;
    		if (nums.size() == 1)
    			return nums[0];
    		map<vector<int>, int>curnums;
    		curnums.insert(pair<vector<int>, int>(nums, 0));
    		int k = -1;
    		k = do_once(curnums);
    		while (k < 0)
    		{
    			k = do_once(curnums);
    		}
    		return k;
    	}
    };
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	
    	int aa[11] = { 7, 9, 8, 0, 7, 1, 3, 5, 5, 2, 3 };
    	vector<int>nums(aa,aa+11);
    	cout << sl.maxCoins(nums);
    	system("pause");
    	return 0;
    }