题目

https://leetcode.com/problems/burst-balloons/

题解

好久不 DP 了，DP 一下吧，结果被坑了很久，看了答案。

递归的时候，我知道分成L，R两边，但是一直按着先删M，再删左右想的，结果删除顺序有依赖。

看了答案之后发现，要先删左右，最后删M。因为：

• 如果最后删M，能确定M的左边一定是L-1，右边一定是R+1
• 如果先删M，就不能确定M-1的右边是什么，也不能确定M+1的左边是什么

class Solution {
    public int maxCoins(int[] nums) {
        int[] arr = new int[nums.length + 2];
        arr[0] = 1;
        arr[arr.length - 1] = 1;
        System.arraycopy(nums, 0, arr, 1, nums.length);

        int[][] dp = new int[nums.length + 2][nums.length + 2];
        for (int[] d : dp) {
            Arrays.fill(d, Integer.MIN_VALUE);
        }
        return process(arr, 1, arr.length - 2, dp);
    }

    // 完整的从L到R（而且L-1,R+1都未被删）能得到的最大结果
    public int process(int[] arr, int L, int R, int[][] dp) {
        if (L > R) return 0;
        else if (dp[L][R] != Integer.MIN_VALUE) {
            return dp[L][R];
        } else if (L == R) {
            dp[L][R] = arr[L - 1] * arr[L] * arr[L + 1];
            return dp[L][R];
        }

        int result = 0;
        for (int M = L; M <= R; M++) { // 对于任意一个M，此时M的左右都是完整的。删除顺序是：先删光M的左边，然后删光M的右边，最后删M
            result = Math.max(result, arr[L - 1] * arr[M] * arr[R + 1] + process(arr, L, M - 1, dp) + process(arr, M + 1, R, dp));
        }

        dp[L][R] = result;
        return result;
    }
}