Burst Balloonsダイナミックプランニングの解

Leetcode第312題、Burst Balloons、この問題はやはり難しいです.後にブログを書いて記録します.まずGiven n balloons,indexed from 0 to n-1.Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 Example:
Input:[3,1,5,8]Output:167 Explanation:nums=[3,1,5,8]-->[3,5,8]-->[8]-->[8]--[]coins=315+358+138+181=167は私の解題構想を記録した:入力は配列であり、気球が爆発するたびに1つの数字が消え、結果としてnums[left]*nums[i]*nums[right].爆発するたびにleftとrightがどの風船なのか分からないのは明らかだ.どうすればいいの?
法一、法暴力を遡って解く.遡及法ですべての解を探し出し,結果の最大の1つをとる.では,問題の解空間は配列中のn個の数字の全配列であるべきである.配列が違うと、Leftとrightが違います.n<=500なので、解空間は最大500!この解は,明らかに時間,複雑度が高すぎる.
結果の上限:500個の数字で、各数字が消えたときに<=100^3である10^6を加えると、結果<=500*10^6=5*10^8
法二、動的計画という問題は動的計画で解くことができるように見える.2 D配列reで答えを格納できることは明らかです.しかし、動的計画の数学式をどのように決定しますか?Re[i][i+k]は、iからi+k番目の数字を消して得られる硬貨とする.では、その数学的関係は、re[i][i+k]=max(re[i][j-1]+re[j+1][i+k]+re[i-1]*re[j]*re[i+k])である.では質問ですが、なぜre[j]はre[i-1]とre[i+k+1]に乗るのでしょうか.j番目と数字を消したときの隣人がi-1とi+k+1で他のものではないことをどのように保証しますか?実際にはre[i][i+k]つまりi番目からi+k番目の数字を消したときに他の数字が消されないように設計すればよい.どうしてこんなことができるのですか.i+kのkを徐々に大きくすることによって計算されるので,これは実際の状況と一致する.実際には、バルーンを消去する順序は、最終結果を変更することなく、i番目からi番目+k番目のバルーンを消去する(kが徐々に増大する)過程を常に調整することができる.コードを添付:

public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] fixedNums = new int[n + 2];
        fixedNums[0] = fixedNums[n + 1] = 1;
        System.arraycopy(nums, 0, fixedNums, 1, n);
        int[][] re = new int[n + 2][n + 2];
        re[0][0] = re[n + 1][n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            re[i][i] = fixedNums[i - 1] * fixedNums[i] * fixedNums[i + 1];
        }
        for (int k = 1; k < n; k++) {
            for (int i = 1; i + k <= n; i++) {
                int re1 = fixedNums[i] * fixedNums[i - 1] * fixedNums[i + k + 1]
                        + re[i + 1][i + k];
                int re2 = fixedNums[i + k] * fixedNums[i - 1] * fixedNums[i + k + 1]
                        + re[i][i + k - 1];
                int ren = Math.max(re1, re2);
                for (int j = i + 1; j < i + k; j++) {
                    int temp = fixedNums[j] * fixedNums[i - 1] * fixedNums[i + k + 1]
                            + re[i][j - 1] + re[j + 1][i + k];
                    ren = Math.max(temp, ren);
                }
                re[i][i + k] = ren;
            }
        }
        return re[1][n];
    }
```java