[!info] related notes 动态规划 区间 DP 与状态机 DP

戳气球

题目链接：https://leetcode.cn/problems/burst-balloons/

关键思路

这题如果想“先戳哪个”，区间会动态变化，很难做。

正确思路是：

枚举区间里最后一个被戳破的气球是谁。

状态

补两个边界气球 1 后，定义：

dp[left][right] = 开区间 (left, right) 内所有气球都戳完能得到的最大分数

转移

枚举最后一个戳的 k：

dp[left][right] = max(
    dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right]
)

JavaScript

var maxCoins = function(nums) {
    const arr = [1, ...nums, 1];
    const n = arr.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    for (let len = 2; len < n; len++) {
        for (let left = 0; left + len < n; left++) {
            const right = left + len;
            for (let k = left + 1; k < right; k++) {
                dp[left][right] = Math.max(
                    dp[left][right],
                    dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]
                );
            }
        }
    }

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