题目描述：
有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，
left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。
注释:
(1) 你可以假设nums[-1] = nums[n] = 1
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
给出[3, 1, 5, 8]
返回167
分析解答：
样例中[3,5,8]，因先吹爆分数为3的气球只能得到两个数相乘的分数，先吹爆分数为5的气球可以得到3个数相乘更优。但是我们可以知道，对于8而言，
先吹3再吹5和先吹5再吹3，都是一样的因为8是最后吹。因为3和5的问题只在[3,5]区间内，跟区间外面没有关系。因此我们可以用区间dp去解决这个问题。
设dp[i][j]表示吹爆编号为 i 到 j 之间所有的气球所能得到的最大分数。如何转移？那么就穷举先吹爆的气球的编号k，但问题在于，先吹爆气球k会使得k-1号和k+1号气球相邻。所以最后吹爆k号气球，
这样dp方程就很好定义了dp[i][j] = dp[i][k-1] + score(k) + dp[k+1][j]。先吹区间[i,k-1]和区间[k+1,j]最后吹k。如果区间[i,k-1]或者[k+1,j]区间现在还不知道结果怎么办，我们可以用记忆化搜索的方式先去求解。
#include<bits/stdc++.h> using namespace std; int num[100],dp[100][100]; //记忆化搜索 int search(int a[],int l,int r) { if(dp[l][r]) return dp[l][r]; int ans=0; for(int k=l;k<=r;k++){ int mid=a[l-1]*a[k]*a[r+1]; int left=search(a,l,k-1); int right=search(a,k+1,r); ans=max(ans,left+mid+right); } dp[l][r]=ans; return dp[l][r]; } int main() { int n; while(scanf("%d",&n)){ memset(num,0,sizeof(num)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&num[i]); num[0]=1,num[n+1]=1; search(num,1,n); printf("%d",dp[1][n]); } }