1.题目

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8]
输出：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

示例 2：
输入：nums = [1,5]
输出：10

提示：
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/burst-balloons

2.思路

（1）动态规划
具体思路参考经典动态规划：戳气球问题。

3.代码实现（Java）

//思路1————动态规划
public int maxCoins(int[] nums) {
    int length = nums.length;
    int[] scores = new int[length + 2];
    //在原始数组两侧添加“虚拟气球”，分数均为1
    scores[0] = scores[length + 1] = 1;
    //初始化scores
    for (int i = 1; i <= length; i++) {
        scores[i] = nums[i - 1];
    }
    //dp[i][j]:表示戳破气球i和气球j之间(不包括i和j)的所有气球，可以获得的最高分数
    int[][] dp = new int[length + 2][length + 2];
    //i:length->0
    for (int i = length; i >= 0; i--) {
        //j:i+1->length + 1
        for (int j = i + 1; j <= length + 1; j++) {
            //最后戳破的气球
            for (int k = i + 1; k < j; k++) {
                /*
                    择优做选择
                    在区间(i, j)中，如果最后戳破气球为k，那么开区间(i, k)和(k, j)的气球都已被戳破
                    最后剩下的气球为k，相邻的就是气球i和气球j，所以这时的得分为 scores[i]*scores[k]*scores[j]                    
                */
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + scores[i] * scores[k] * scores[j]);
            }
        }
    }
    return dp[0][length + 1];
}