⭐算法OJ⭐ 戳气球【动态规划】Burst Balloons

问题描述

LeetCode 312. 戳气球（Burst Balloons）
给定 n 个气球，编号从 0 到 n-1，每个气球上标有一个数字 nums[i]。戳破气球 i 可以获得 nums[left] * nums[i] * nums[right] 的硬币（left 和 right 是 i 的相邻气球）。戳破后，left 和 right 变成相邻。求能获得的最大硬币数量。

解题思路

这是一个典型的动态规划问题。关键在于如何定义子问题和状态转移方程。

关键观察

• 逆向思考：与其考虑先戳哪个气球，不如考虑最后戳哪个气球。这样左右两边的气球就不会相互影响。
• 区间DP：定义 dp[i][j] 表示戳破区间 (i,j) 内所有气球能获得的最大硬币数（不包括 i 和 j 本身）。
• 边界处理：在数组前后各添加一个虚拟气球，值为1，方便计算。

动态规划步骤

• 状态定义：dp[i][j] 表示戳破开区间 (i,j) 内所有气球能获得的最大硬币数。
• 初始化：当 i >= j-1 时，dp[i][j] = 0（区间内没有气球可戳）。
• 状态转移：
  • 对于区间 (i,j)，假设最后一个戳破的气球是 k（i < k < j）
  • 则 dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j])
• 最终结果：dp[0][n+1]（因为我们添加了两个虚拟气球）

C++ 代码实现

int maxCoins(vector<int>& nums) {int n = nums.size();vector<int> new_nums(n + 2, 1);  // 前后各添加一个1for (int i = 1; i <= n; ++i) {new_nums[i] = nums[i - 1];}// dp[i][j] 表示戳破(i,j)区间内所有气球的最大硬币数vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));// 区间长度从 1 到 nfor (int len = 1; len <= n; ++len) {// 左边界 i 从 0 到 n - lenfor (int i = 0; i <= n - len; ++i) {int j = i + len + 1;  // 右边界if (j > n + 1) continue;// 枚举最后一个戳破的气球kfor (int k = i + 1; k < j; ++k) {dp[i][j] = max(dp[i][j], new_nums[i] * new_nums[k] * new_nums[j] + dp[i][k] + dp[k][j]);}}}return dp[0][n + 1];
}

复杂度分析

• 时间复杂度：$O(n^3)$，三重循环。
• 空间复杂度：$O(n^2)$，DP数组的大小。