戳气球问题_戳气球 算法

戳气球问题本质上可以认为是一种组合+逆推的问题（背包问题模型）

 我们可以有两种方法

1.dfs爆搜法

2.dp法

1.dfs爆搜法

dfs爆搜就是暴力枚举出哪个先破，哪个后破，直到找出最佳的方案

本质上是一个全排列问题，但是全排列问题时间复杂度是O（10的n次方），不适合本题，所以我们采用dp更好

#include <iostream>
using namespace std;
int n;
int ans = 0;
int w[1001];
int visit[1002];
void dfs(int x, int sum)
{//x表示选了几个，sum表示现在的奖励总和
	if (x >= n)
	{
		ans = max(ans, sum);
		return;
	}
	for (int i = 1;i <= n;i++)
	{
		if (!visit[i])
		{
			visit[i] = 1;
			int L=1, R=2;
			for (int k = i - 1;k >= 0;k--)
				if (!visit[k])
				{
					L = k; break;
				}
			for (int k = i + 1;k <= n+1;k++)
				if (!visit[k])
				{
					R = k; break;
				}
			dfs(x + 1, sum + w[i]*w[L]*w[R]);
			visit[i] = 0;
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
		cin >> w[i];
	w[0] = w[n + 1] = 1;
	//先戳破第一个
	for (int i = 1;i <= n;i++)
	{
		if (!visit[i])
		{
			visit[i] = 1;
			int L=0, R=n+1;
			for (int k = i - 1;k >= 0;k--)
				if (!visit[k])
				{
					L = k; break;
				}
			for (int k = i + 1;k <=n+1;k++)
				if (!visit[k])
				{
					R = k; break;
				}
			dfs(1, w[i]*w[L]*w[R]);
			visit[i] = 0;
		}
	}
	cout << ans;
}

2.dp法

我们可以先假设两个虚拟节点，第0结点和第n+1结点，他们的奖励都是1

下面分析一下假设k是最后一个被戳破的气球

 在(i,k)区间中，由于全部被戳破，他的最大奖励是dp[i][k]

在(k,j)区间中，由于全部被戳破，他的最大奖励是dp[k][j]

此时k的左节点是  第i个结点，k的右节点是  第j个结点

 

那么可以得到一个基本框架

for（遍历所有i）
    for（遍历所有j）
        for（i<k<j)
            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+w[i]*w[k]*w[j]);

 最后的答案就是dp[0][n+1]，表示0~n+1区间获得的最大奖励值

所以我们只要确保计算dp[i][j]的时候，dp[i][k]和dp[k][j]已经计算出来了即可

所以i是从下往上遍历的，j是从左往右遍历的

 下面给出代码

#include <iostream>
using namespace std;
const int N = 1005;
int dp[N][N];
int s[N];
int main()
{
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		cin >> s[i];
	}
	s[0] = s[n + 1] = 1;
	//两个虚拟结点
	//dp[i][j]表示开区间（i，j）的最大奖励
	for (int i = n - 1;i >= 0;i--)							//i从倒数第二个开始，遍历到0
		for (int j = i + 2;j <= n + 1;j++)					//由于开区间，(i,j)至少应包含一个，遍历到n+1
		{
			for (int k = i + 1;k < j;k++)					//开区间，k表示i的下一个，k不会到达j,因为开区间，j取不到
				dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + s[i] * s[j] * s[k]);
		}
	cout << dp[0][n + 1];
}