题解 | #打气球的最大分数#

//由左边的暴力递归版本改成动态规划的版本
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
      
    int *arr=new int[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int help[n+2];//辅助数组第一个和最后一个设置为1
    help[0]=1;
    help[n+1]=1;
    for(int i=1;i<n+1;i++)
        help[i]=arr[i-1];
        //建立dp表
        int dp[n+2][n+2];//动态规划表 
        //根据base case填初始值
        //由题意可以发现dp表的第一行和最后一行第一列和最后一列时用不到的
        for(int i=1;i<n+1;i++)
        dp[i][i]=help[i]*help[i-1]*help[i+1];//填好主对角线上的值
        //开始填base case以外的普通位置
        //分析知对一个普遍位置来说需要知道它左边和下边的值
        //所以dp表填写的顺序为从下到上从左到右而且因为left和right是数组的范围
        //所以left一定不可能大于right所以主对角线以下的位置全都无效
        for(int i=n;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                //递归是怎么求的每个位置的值，这里就怎么求
                 int max=0;
            //先把最左侧和最右侧气球最后被打爆时的情况做对比
                 int temp=help[i]*help[i-1]*help[j+1]+dp[i+1][j];
                 max=max>temp?max:temp;
                 temp=help[j]*help[j+1]*help[i-1]+dp[i][j-1];
                 max=max>temp?max:temp;
                 //比较中间位置
                  for(int k=i+1;k<j;k++){
                     temp=help[k]*help[i-1]*help[j+1]+dp[i][k-1]+dp[k+1][j];
                     max=temp>max?temp:max;
                    }
                    dp[i][j]=max;
            }
        } 
    cout<<dp[1][n]<<endl;
    return 0;
}