算法题：戳气球问题
问题描述
nums，戳破第 i 个气球可以获得的金币为 nums[i-1] * nums[i] * nums[i+1]。如果气球的左边或右边没有气球，视为 1。你需要计算出最多能获得的金币数。程序员视角解析
动态规划拆解
dp[i][j]，表示在开区间 (i, j) 中戳破所有气球能获得的最多金币。注意，i 和 j 是开区间，所以 i 和 j 的气球不会被戳。为了计算
dp[i][j]，我们需要枚举开区间 (i, j) 中的每一个气球 k，把它作为最后一个被戳的气球。此时，分值由三部分组成：戳破气球 k的金币：nums[i] * nums[k] * nums[j]。dp[i][k]：戳破(i, k)开区间内的所有气球的最大金币。dp[k][j]：戳破(k, j)开区间内的所有气球的最大金币。
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
边界条件
1，所以实际计算的数组是 nums = [1] + nums + [1]。初始状态下，区间长度为 1 或更小的 dp[i][j] 都是 0，因为没有气球可以戳。动态规划代码实现
public class BurstBalloons {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newNums = new int[n + 2];
newNums[0] = newNums[n + 1] = 1;
System.arraycopy(nums, 0, newNums, 1, n);
int[][] dp = new int[n + 2][n + 2];
for (int len = 2; len <= n + 1; len++) { // 区间长度
for (int i = 0; i <= n + 1 - len; i++) {
int j = i + len; // 区间右端点
for (int k = i + 1; k < j; k++) { // 枚举最后一个气球
dp[i][j] = Math.max(dp[i][j],
dp[i][k] + dp[k][j] + newNums[i] * newNums[k] * newNums[j]);
}
}
}
return dp[0][n + 1];
}
public static void main(String[] args) {
BurstBalloons bb = new BurstBalloons();
int[] nums = {3, 1, 5, 8};
System.out.println("Maximum coins: " + bb.maxCoins(nums)); // 输出：167
}
}
核心代码讲解
扩展数组：在原数组两边加上 1，这样方便处理边界问题。区间遍历：通过区间长度和起点，遍历所有可能的 (i, j)开区间。枚举最后一个气球：关键在于选对 k，也就是最后一个被戳破的气球。
💡 想象一下，选定最后一个气球后，开区间(i, j)就被分成了两半，问题也就被分解了。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
