首页 > 试题广场 >

打气球的最大分数

[编程题]打气球的最大分数
  • 热度指数：2189 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数组arr,长度为n。代表排有分数的气球。 每打爆一个气球都能获得分数，假设打爆气球的分数为X，获得分数的规则如下:
1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L:如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为R.获得分数为L*X*R
2)如果被打爆的气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L:如果被打爆气球的右边所有气球都已经被打爆，获得分数为L*X。
3)如果被打爆气球的左边所有的气球都已经被打爆:如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球。获得分数为X*R.
4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为X。
目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。

输入描述:
输出包括两行，第一行包括一个整数n（0<=n<=500），第二行包括n个整数，代表数组arr （1<=arr[i]<=100）。


输出描述:
输出包括一个整数，代表可能获得的最大分数。
示例1

输入

3
3 2 5

输出

50

说明

2->1->3  3*2*5+3*5+5=50
示例2

输入

8
23 4 45 65 23 43 54 56

输出

639019

备注:
时间复杂度,空间复杂度。
算法知识视频讲解
添加回答
_Edison头像 _Edison
主要思路就是动态规划 dp[i][j]表示从第i个位置开始到第j个位置结束的区间内打气球能够得到的最大分数。我们从每个区间的长度开始递推，最外层循环表示的是区间长度，第二层循环表示起始位置，第三层循环表示在该区间内最后打爆气球的位置。 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<long long> a(n+2);
	vector<vector<long long>> dp(n+2,vector<long long>(n+2));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
    a[0] = 1;
    a[n+1] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i][i] = a[i-1]*a[i]*a[i+1];
	}
  
    for(int i=1;i<n;i++){
        for(int j=1;j<=n-i;j++){
            for(int k=j;k<=j+i;k++){
                dp[j][j+i] = max(dp[j][j+i],a[k]*a[j-1]*a[j+i+1]+dp[j][k-1]+dp[k+1][j+i]);
            }
        }
    }

	cout << dp[1][n] << endl;
	return 0;
}


发表于 2020-01-04 06:32:23 回复(0)
Java
pein531头像 pein531
0这个用例是真的可耻啊，0没意义也就算了，你连第二行都不输入，那输入格式都不统一了。这个题是一个范围上的尝试模型，为了编程上的方便，我们对气球数组的首尾补充两个1，防止打爆端点气球时没有邻居分数可以乘从而导致边界问题。假设有一个函数f(L,R)表示将L~R上的所有气球都打爆的最大得分，很容易可以想到两个尝试方向：
  1. 在L~R的范围上，尝试先打爆位置i的气球，此时打爆它会乘走i-1和i+1的分值，如果下一次去打i+1位置的气球，此时i位置的气球已经不在了，可我们在决定打i+1位置的气球时，这件事无从得知。所以会存在某个位置，当我们决定要打爆该位置上的气球时并不能确定它此时的左右邻居是哪个气球，因此无法计算打爆它所带来的收益。
  2. 在L~R的范围上，尝试最后打爆位置i的气球，既然是最后打爆i位置的气球，那么在此之前肯定我们需要先把L~i-1和i+1~R上的气球打完。这样就能够调用f(L,i-1)和f(i+1,R)，当前i位置气球的分值乘上L-1和R+1位置气球的分值+这两个区间上打气球的得分就是f(L,R)。
因此我们很容易发现，第二种尝试才能够确定打爆i位置的气球时能够获得的收益（因为知道它的左右两边都是哪个气球）。此问题存在两个变化的端点L和R，是个二维动态规划问题，这里提供一个把暴力递归改成记忆化搜索的版本。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n == 0){
            System.out.println(0);
        }else{
            String[] strArr = br.readLine().split(" ");
            int[] arr = new int[n + 2];
            arr[0] = 1;
            arr[arr.length - 1] = 1;
            for(int i = 1; i <= n; i++){
                arr[i] = Integer.parseInt(strArr[i - 1]);
            }
            int[][] memory = new int[arr.length][arr.length];
            System.out.println(burstBalloons(arr, 1, n, memory));
        }
    }
    
    private static int burstBalloons(int[] arr, int left, int right, int[][] memory) {
        if(memory[left][right] > 0) return memory[left][right];
        if(left == right){
            // 区间上只有一个数，直接返回
            return arr[left - 1] * arr[left] * arr[right + 1];
        }
        // 尝试最后打爆所有位置，选择最大的得分
        memory[left][right] = Math.max(arr[left - 1]*arr[left]*arr[right + 1] + burstBalloons(arr, left + 1, right, memory),
                                       arr[left - 1]*arr[right]*arr[right + 1] + burstBalloons(arr, left, right - 1, memory));
        for(int i = left + 1; i < right; i++){
            memory[left][right] = Math.max(memory[left][right], arr[left - 1]*arr[i]*arr[right + 1] + burstBalloons(arr, left, i - 1, memory) + burstBalloons(arr, i + 1, right, memory));
        }
        return memory[left][right];
    }
}

编辑于 2021-12-08 14:01:04 回复(0)
FrankChan头像 FrankChan
dp[i][j]表示[i...j]左右的灯全亮着，打爆[i...j]范围内的灯所获得的最高分数。左神的书上用了一个很巧妙的技巧，让首尾补1，2颗常亮的大灯泡，让dp[1][n]顺利地成为最终问题的解。

要获得[i...j]范围dp[i][j]的最大值，需要逐一尝试最后一个打破k( i<= k <= j)，获取其中的最大分数为dp[i][j]的值。如果k是最后打破灯，那dp[i][j]可以分为三个部分，左边dp[i][k-1]，右边dp[k+1][j]的分数，最后打爆k时获得的分数是arr[i-1] * arr[k] * arr[j+1]，总分为：
dp[i][j] = dp[i][k-1] + arr[i-1] * arr[k] * arr[j+1] + dp[k+1][j].
遍历k时取最大值：
dp[i][j] = max{dp[i][k-1] + arr[i-1] * arr[k] * arr[j+1] + dp[k+1][j]}      { i<=k <= j}.
通常的题解会分别处理dp[i][j]的边界，即最后打爆i和j时单独处理，其实是可以取巧的，最后打爆i时
dp[i][k-1] == dp[i][i-1]为0，最后打爆j时同理，因此可以统一起来。 
#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 2, 1); //首尾补1，主要是处理边界问题，参考了左神的书上的思路
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    //dp[i][j]表示[i...j]左右的灯全亮，打爆[i...j]范围内的灯所能获得的最大分数
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for(int i = n; i >= 1; i--) {//从最右边往回考查
        for(int j = i; j <= n; j++) {//逐次求dp[i][i], dp[i][i+1], ..., dp[i][n]
            for(int k = i; k <= j; k++) {//依此计算如果[i...j]中第k个灯最后打爆的情形
                //在处理[i...j]中的i和j边界时，由于dp[i][i-1] = 0，dp[j+1][j] = 0, 不影响结果，因此统一处理
                int cur = dp[i][k-1] + dp[k+1][j] + arr[i-1] * arr[k] * arr[j+1];
                dp[i][j] = max(cur, dp[i][j]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}


编辑于 2020-04-20 23:20:27 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n+2];
    a[0] = a[n+1] = 1;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int dp[n+2][n+2];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[i][i] = a[i-1]*a[i]*a[i+1];
    for(int l=n;l>=1;l--)
        for(int r=l+1;r<=n;r++){
            dp[l][r] = max(dp[l+1][r]+a[l-1]*a[l]*a[r+1], dp[l][r-1]+a[l-1]*a[r]*a[r+1]);
            for(int i=l+1;i<=r-1;i++)
                dp[l][r] = max(dp[l][r], dp[l][i-1]+dp[i+1][r]+a[l-1]*a[i]*a[r+1]);
        }
    cout<<dp[1][n]<<endl;
    return 0;
}

发表于 2020-02-14 00:21:47 回复(0)
C++
木子蓝色头像 木子蓝色
区间DP问题 
#include <bits/stdc++.h>

using namespace std;

/*
区间DP：令状态 dp[i, j] 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，
那么 dp[i, j] = max(dp[i, j], dp[i, k] + dp[k + 1, j] + cost)，
cost 为将这两组元素合并起来的代价。 
*/
int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    // nums首尾添加1，方便处理边界情况
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    // dp[i][j] 表示开区间 (i,j) 内你能拿到的最多分数，注意是 开区间(i, j)
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    // i 要倒序遍历
    // 因为动态规划在求解子问题一定要在父问题之前
    // i 在[0, n - 1] 之间倒序遍历
    for(int i = n - 1; i >= 0; --i){
        // j 在[i + 2, n + 1]
        for(int j = i + 2; j <= n + 1; ++j){
            // x 在 [i + 1, j - 1]
            for(int x = i + 1; x < j; ++x){
                dp[i][j] = max(dp[i][j], dp[i][x] + dp[x][j] + (nums[i] * nums[x] * nums[j]));
            }
        }
    }
    cout << dp[0][n + 1];    
    return 0;
}


发表于 2022-04-07 21:02:15 回复(0)
futuer头像 futuer
n == 0 输出0。
发表于 2021-03-22 00:36:44 回复(0)
牛客709460432号头像 牛客709460432号 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> arr(n+2,1);
    for(int i = 1; i <= n; ++i)
        cin >> arr[i];
    vector<vector<int>> dp(n+2,vector<int>(n+2,0));
    for(int i = n-1; i >= 0; --i){
        for(int j = i+2; j <= n+1; ++j){
            for(int k = i+1; k < j; ++k){
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j]);
            }
        }
    }
    cout << dp[0][n+1] << endl;
}

发表于 2020-07-01 18:10:48 回复(0)
我要收offer头像 我要收offer
已经可以通过100%测试用例了。
此题考查的是将递归转化为动态规划。递归就不粘贴了。
参考左神的书籍，分布在数组两端添加了一个1。
dp的定义和书上稍有不同。所以核心代码稍稍简洁一些。 
dp = new int[n+2][n+2]
dp[i][j]表示将子数组arr[i~j]中气球都打爆的最大分数。其中位置为i、j的气球不打爆。
最终输出dp[0][n+1]。
矩阵dp的主对角线以及该斜线上面的对角线都是0，主对角线下面的当然也都是0。这些都不用计算。
dp的计算是自下而上，从左往右逐一计算。
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(bf.readLine());
        if(n == 0){
            System.out.println(0);
            bf.close();
            return;
        }
        String[] strs = bf.readLine().split(" ");
        int[] arr = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.valueOf(strs[i - 1]);
        }
        bf.close();
        
        arr[0] = 1;
        arr[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
                
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + (arr[i] * arr[k] * arr[j]));
                }
            }
        }
        System.out.println(dp[0][n + 1]);
    }
}


编辑于 2020-06-03 23:01:02 回复(3)
Learn2Learn头像 Learn2Learn
python会超时，还是用c++过吧 
#include "iostream"
#include "vector"
#include "algorithm"
  
using namespace std;
  
int main()
{
    int n;
    cin >> n;
    if(n == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    vector<int> arr(n + 2);
    arr[0] = arr[n + 1] = 1;
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++)
    {
        dp[i][i]=arr[i-1]*arr[i]*arr[i+1];
    }
  
    for (int len = 0; len <= n - 1; len++)
    {
        for (int l = 1; l <= n -len; l++)
        {
            int r = l + len;
            for (int k = l; k <= r; k++)
            {
                dp[l][r] = max(dp[l][r], arr[k] * arr[l-1] * arr[r+1]
                               + dp[l][k-1] + dp[k+1][r]);
            }
        }
    }
  
  
    cout << dp[1][n] << endl;
    return 0;
}


发表于 2019-09-06 17:05:58 回复(0)
提交观点

问题信息

动态规划 数学
上传者：小小
难度：
9条回答 5774浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号