打气球的最大分数

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)。

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];
    }
}