312. 戳气球

有 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 <= 300
• 0 <= nums[i] <= 100

动态规划

简单的动态规划的最后一步是固定的，难的动态规划的最后一步不固定，但依然有个取值范围。也难不到哪里去。

根据状态转移方程、base case和最终状态确定遍历顺序。

dp 数组的含义：dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x。

由于是开区间，dp[i][k] 和 dp[k][j] 不会影响气球 k；而戳破气球 k 时，旁边相邻的就是气球 i 和气球 j 了，最后还会剩下气球 i 和气球 j，这也恰好满足了 dp 数组开区间的定义。

拿这道题举例，dp[i][j] 所依赖的状态是 dp[i][k] 和 dp[k][j]，那么我们必须保证：在计算 dp[i][j] 时，dp[i][k] 和 dp[k][j] 已经被计算出来了（其中 i < k < j）。

最终状态就是指题目要求的结果，对于这道题目也就是 dp[0][n+1]。

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        
        // 添加两侧的虚拟气球
        int[] points = new int[n + 2];
        // 重点。题目说如果 `i - 1`或 `i + 1` 超出了数组的边界，那么就当它是一个数字为 `1` 的气球。
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }
        
        // base case 已经都被初始化为 0
        // dp[i][j] 表示戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数
        int[][] dp = new int[n + 2][n + 2];
        // 开始状态转移
        // i 应该从下往上，i最小是0，最大是n。因为i是开区间(i,j)的左边界
        for (int i = n; i >= 0; i--) {
            // j 应该从左往右，j最大是n+1，最小是1。因为j是开区间(i,j)的右边界
            for (int j = i + 1; j < n + 2; j++) {
                // 最后戳破的气球是哪个？
                // 因为k大于i小于j，第i行依赖于第k行，第j列依赖于第k列，所以i要倒序遍历，j要正序遍历
                // points[0]和points[n+1]是虚拟气球，值为1。
                for (int k = i + 1; k < j; k++) {
                    // 择优做选择
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]
                    );
                }
            }
        }
        // (0...n+1)区间的结果。
        return dp[0][n + 1];
    }
}

去除冗余操作，i最小是0，最大是n-1，j最大是n+1，最小是2：

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;

        // 添加两侧的虚拟气球
        int[] points = new int[n + 2];
        points[0] = points[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }

        // base case 已经都被初始化为 0
        int[][] dp = new int[n + 2][n + 2];
        // 开始状态转移
        // i 应该从下往上，i最小是0，最大是n-1
        for (int i = n - 1; i >= 0; i--) {
            // j 应该从左往右，j最大是n+1，最小是2
            for (int j = i + 2; j < n + 2; j++) {
                // 最后戳破的气球是哪个？因为k大于i小于j，所以i要倒序遍历，j要正序遍历
                for (int k = i + 1; k < j; k++) {
                    // 择优做选择
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]);
                }
            }
        }
        return dp[0][n + 1];
    }
}

时间复杂度O(n^3)

空间复杂度O(n^2)