Burst Balloons

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

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:

(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = \[3,1,5,8\] --> \[3,5,8\] -->   \[3,8\]   -->  \[8\]  --> \[\]

coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Thoughts

给定一个数组，元素值代表收益，每次选择一个元素去掉，得到的收益为它当前的左边元素它它右边元素。action为选择一个元素k去掉，相当于根据k做划分。如果正着想很难理清状态，但倒着可以知道最后一次只会爆掉一个元素k，因此让dp[j][i]表示爆j和i之间的(不包括i和j)所有气球能获得的最大收益，让k表示j和i之间中最后一个爆掉的气球, 那么爆k时的收益为coins[j] coins[k] coins[i] + dp[j][k] + dp[k][i]。 让k在[j + 1, i - 1]依次遍历即可。

Code

/*
 * @lc app=leetcode id=312 lang=cpp
 *
 * [312] Burst Balloons
 */
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        const int N = nums.size();
        vector<int> coins(N + 2);
        coins[0] = coins[N + 1] = 1;
        for (int i = 0; i < N; ++i) {
            coins[i + 1] = nums[i];
        }
        vector<vector<int>> dp(N + 2, vector<int>(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 - 1; ++k) {
                    dp[i][j] = max(dp[i][j], coins[i] * coins[k] * coins[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][N + 1];
    }
};

class Solution {
    public int maxCoins(int[] nums) {
        int[] coins = new int[nums.length + 2];
        int n = 1; 
        for (int num : nums) {
            if (num != 0) {
                coins[n++] = num;
            }
        }

        coins[0] = coins[n++] = 1;
        int[][] f = new int[n][n];
        for (int i = 2; i < n; i++) {
            for (int j = i - 2; j >= 0; j--) {
                for (int k = j + 1; k <= i - 1; k++) {
                    f[j][i] = Math.max(f[j][i],
                                             coins[j] * coins[k] * coins[i] + f[j][k] + f[k][i]);
                }
            }
        }

        return f[0][n - 1];
    }
}

Analysis

Errors:

1. j从小到大遍历

时间复杂度O(N^3), 空间O(N^2).