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

打气球的最大分数

http://www.nowcoder.com/practice/35119064d0224c35ab1ab612bffee8df

//由左边的暴力递归版本改成动态规划的版本
#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;
}
全部评论
//暴力递归版本 #include<bits> using namespace std; //该递归函数的含义为: //打爆left到right所有的气球返回可能获得的最大分数 int process(int arr[],int left,int right); int main(){ int n; cin>>n; int *arr=new int[n]; for(int i=0;i<n>>arr[i]; int help[n+2];//辅助数组第一个和最后一个设置为1 help[0]=1; help[n+1]=1; for(int i=1;i<n>temp?max:temp; temp=arr[right]*arr[right+1]*arr[left-1]+process(arr, left, right-1); max=max>temp?max:temp; //比较中间位置 //如果i位置是最后被打爆的时候此时的最大值为 for(int i=left+1;i<right>max?temp:max; } return max; }</right></n></n></bits>
点赞
送花
回复 分享
发布于 2022-02-14 18:46

相关推荐

流岚噗噗:肯定直接说第一啊,网上的身份都是自己给的好吧
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务