戳气球问题本质上可以认为是一种组合+逆推的问题（背包问题模型）
我们可以有两种方法
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从倒数第二个开始，遍历到0for (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];
}
