题意：有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。
思路：表示吹爆所有在区间的气球，所能得到的最大分数。那么如何进行状态转移？假设吹爆第k个气球，那么k-1和k+1个气球变得相邻，不方便转移。那么我们就先吹爆区间和区间的所有气球，最后再来吹爆第k个气球，那么这样就十分方便转移了。枚举k的位置，
AC代码
#include <cstdio>#include <cmath>#include <cctype>#include <bitset>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int>typedef long long LL;const int maxn = 500 + 5;int a[maxn];int dp[maxn][maxn], vis[maxn][maxn];int maxScore(int l, int r) { if(vis[l][r]) return dp[l][r]; int res = 0; for(int k = l; k <= r; ++k) { int mid = a[l-1]*a[k]*a[r+1]; int left = maxScore(l, k-1); int right = maxScore(k+1, r); res = max(res, left+mid+right); } return res;}int main() { int n; while(scanf("%d", &n) == 1) { for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); a[0] = a[n+1] = 1; memset(vis, 0, sizeof(vis)); printf("%d\n", maxScore(1, n)); } return 0;}如有不当之处欢迎指出！
