🌕🌕🌗 312. 戳气球

难度: 🌕🌕🌗

问题描述

---

解法

class Solution {
    public int maxCoins(int[] nums) {
        // 思路：
        // dp[i][j] - [i, j] 区间能获得的最大硬币数
        // dp[i][j] = dp[i][k - 1] + [i - 1] * [k] * [j + 1] + dp[k + 1][j]
        // 问：
        // 假设戳破 k 下标的气球，那么剩余数组就是 [i, k - 1] & [k + 1, j] 形成的新数组，这个新数组的最大硬币数又如何求？
        // 其实这种戳破顺序就是正向戳破顺序，导致 [i, k - 1] & [k + 1, j] 关联，互相影响，无解
        // ∴需要保证 k 是最后一个戳破的气球，也可以理解为 k 为添加的新气球的下标，这样 [i, k - 1] & [k + 1, j] 就不相干了
        // 可以各自计算自己区间的最大硬币数
        // 问：
        // 为什么是 [i - 1] * [k] * [j + 1] 而不是 [k - 1] * [k] * [k + 1]
        // [k] 为最后戳破的气球，现加上 [k] 后，形成的新数组是 [i - 1, k, j + 1] 
        // ∴ 添加 [k] 后获得的硬币数为  [i - 1] * [k] * [j + 1]
        // 此外，要求 dp[i][j] 则前提是得到 
        // 1. dp[i][k - 1] --> 同一行前面的元素
        // 2. dp[k + 1][j] --> 同一列下面的元素
        // ∴ dp 的顺序应该为 从下往上，然后同一行从左到右
        int len = nums.length;
        int[] array = new int[len + 2];
        array[0] = 1;
        array[len + 1] = 1; // 虚拟哨兵节点
        for(int i = 0; i < len; i ++) {
            array[i + 1] = nums[i];
        }
        // dp
        int size = len + 2; // 新数组对应的长度
        int[][] dp = new int[size][size];
        // 原数组 [0, len - 1] --> 新数组 [1, len] --> [1, size - 2] 有效
        for(int i = len; i >= 1; i --) {
            // 从下往上遍历
            for(int j = i; j <= len; j ++) {
                // 同行从左向右遍历
                // 当前可戳破气球边界 [i, j]
                for(int k = i; k <= j; k ++) {
                    // dp[i][j] 取不同戳破下标处的最大硬币数
                    dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + array[i - 1] * array[k] * array[j + 1] + dp[k + 1][j]);
                }
                // System.out.println(i + " " + j  + " " + dp[i][j]);
            }
        }
        return dp[1][len];
    }
}

---

输出