ac

给定一个数组arr,长度为n。代表排有分数的气球。 每打爆一个气球都能获得分数，假设打爆气球的分数为X，获得分数的规则如下:
1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L:如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为R.获得分数为L*X*R
2)如果被打爆的气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L:如果被打爆气球的右边所有气球都已经被打爆，获得分数为L*X。
3)如果被打爆气球的左边所有的气球都已经被打爆:如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球。获得分数为X*R.
4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为X。
目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。

时间复杂度O(n^{3}),空间复杂度O(n^{2})

3 2 5

左右补充1: 1 3 2 5 1

第一步：(必须考虑左右情况)
dp[1][1]=3*2=6, dp[2][2]=3*2*5=30,dp[3][3]=2*5=10

第二步：(必须考虑左右情况)
dp[1][2] = dp[2][2] + 再处理1 = 30 + 15 = 45
         = dp[1][1] + 再处理2 = 6 + 10 = 16
         = 45

dp[2][3] = dp[2][2] + 再处理3 = 30 + 15 = 45
         = dp[3][3] + 再处理2 = 10 + 6 = 16
         = 45

第二步：(必须考虑左右情况)
dp[1][3] = dp[1][2] + 再处理3 = 45 + 5 = 50
         = dp[2][3] + 再处理1 = 45 + 3 = 48
         = dp[1][1] + dp[3][3] + 再处理2 = 6 + 10 + 2 = 18
         = 50

import java.util.Scanner;

public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        // 方便处理，前后增加一个1
        int[] arr = new int[n+2];
        arr[0] = 1;
        arr[n+1] = 1;
        for(int i=1;i<=n;i++){
            arr[i] = sc.nextInt();
        }
        // 0 1 ... n n+1
        int[][] dp = new int[n+2][n+2];
        // dp[i..i] 的求解就方便了
        for(int i=1;i<=n;i++){
            dp[i][i] = arr[i-1] * arr[i] * arr[i+1];
        }
        // dp[i][j]距离为0的求解了，接下来求距离为1,2...的，即如下3个元素
        // 先求：11 22 33
        // 接着求：12 23
        // 最后求：13 (最后的结果)
        for(int k=1;k<n;k++){
            for(int i=1;i<=n;i++){
                // 求dp[l][r]
                int l = i;
                int r = i + k;
                if(r > n){
                    continue;
                }
                // dp[l][r-1] ... dp[l+1][r]等是已经求出来了的，就是距离是k-1的是已经求解出来了的
                // 这里循环代表，先打爆哪一个
                for(int j=l;j<=r;j++){ // 最后打爆j
                    dp[l][r] = Math.max(dp[l][r],
                            dp[l][j-1] + dp[j+1][r] + arr[l-1] * arr[j] * arr[r+1]);
                }
            }
        }
        System.out.print(dp[1][n]);
    }

}
/*
3
3 2 5

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

8
23 4 45 65 23 43 54 56

639019
 */