戳气球问题（基础版本）

字数 1951 2025-10-27 17:41:11

戳气球问题（基础版本）

题目描述：
给定一组气球，每个气球上标有一个数字。当你戳破一个气球时，你可以获得一定数量的硬币，具体规则是：戳破第i个气球时，你可以获得nums[left] * nums[i] * nums[right]枚硬币。这里left和right是与第i个气球相邻的气球的索引。戳破气球i后，气球left和气球right会变成相邻的气球。你的目标是选择戳破气球的顺序，使得获得的硬币总数最大。

注意：

你可以假设nums[-1] = nums[n] = 1，但它们在数组中并不真实存在，因此不会影响你的戳破操作。
0 ≤ n ≤ 300，其中n是气球的数量。
每个气球上的数字在[0, 100]的范围内。

解题过程：

问题分析：
这个问题看似简单，但戳破一个气球后，数组的相邻关系会改变，这使得直接使用贪心策略（例如每次都戳破数字最小的气球）会失败。我们需要找到一个戳破顺序，使得总收益最大。区间动态规划是解决这类问题的有效方法。
关键思路转变：
直接思考“先戳破哪个气球”是困难的，因为戳破一个气球后，左右两边的气球会变得相邻，破坏了原有的区间结构。一个更巧妙的思路是：考虑最后一个被戳破的气球。如果我们能确定最后一个被戳破的气球k，那么在戳破k之前，区间[i, k-1]和[k+1, j]的气球已经被戳破，并且由于k是最后一个被戳破的，此时与k相邻的就是区间边界外的两个“虚拟气球”nums[i-1]和nums[j+1]。因此，戳破k获得的硬币就是nums[i-1] * nums[k] * nums[j+1]。
定义状态：
定义dp[i][j]表示戳破区间[i, j]内所有气球（注意，区间两端的边界气球i-1和j+1还没有被戳破）所能获得的最大硬币数。
- 为了处理边界情况，我们可以在原始数组nums的首尾各添加一个1，即创建一个新数组vals，其中vals[0] = vals[n+1] = 1，vals[1..n] = nums[0..n-1]。这样，区间[1, n]就是我们要处理的所有气球。
状态转移方程：
对于区间[i, j]，我们枚举这个区间内最后一个被戳破的气球k（i <= k <= j）。
- 在戳破k之前，区间[i, k-1]和[k+1, j]内的气球必须已经被戳破。由于k是最后一个被戳破的，此时与k相邻的就是区间[i, j]的边界外的两个气球，即vals[i-1]和vals[j+1]。
- 因此，戳破k获得的硬币是vals[i-1] * vals[k] * vals[j+1]。
- 那么，总收益就是：戳破左边区间[i, k-1]的最大收益 + 戳破k的收益 + 戳破右边区间[k+1, j]的最大收益。
- 状态转移方程为：
  dp[i][j] = max(dp[i][j], dp[i][k-1] + vals[i-1]*vals[k]*vals[j+1] + dp[k+1][j])，其中k从i遍历到j。
边界条件与初始化：
- 当区间长度为0（即i > j）时，dp[i][j] = 0，因为没有气球可戳。
- 当区间长度为1（即i == j）时，dp[i][j] = vals[i-1] * vals[i] * vals[i+1]，因为此时k只能是i，且左右区间均为空。
计算顺序：
由于计算dp[i][j]时需要用到dp[i][k-1]和dp[k+1][j]，即区间长度更小的子区间的结果，因此我们需要按照区间长度从小到大的顺序进行计算。先计算所有长度为1的区间，然后是长度为2的区间，依此类推，直到长度为n的区间[1, n]。
最终结果：
我们的目标是戳破所有气球，即区间[1, n]，因此最终结果为dp[1][n]。

示例（用于理解）：
假设气球数字为[3, 1, 5, 8]。

构建vals数组为[1, 3, 1, 5, 8, 1]（n=4）。
我们需要计算dp[1][4]。
例如，当k=3（即值为5的气球）作为最后一个被戳破时：
- 左边区间[1,2]（气球3和1）的最大收益为dp[1][2]。
- 右边区间[4,4]（气球8）的最大收益为dp[4][4]。
- 戳破k=3的收益为vals[0]*vals[3]*vals[5] = 1*5*1 = 5。
- 总收益为dp[1][2] + 5 + dp[4][4]。
我们需要枚举k=1,2,3,4，取最大值作为dp[1][4]。

通过这种区间动态规划的方法，我们可以系统地计算出所有可能戳破顺序中的最大收益。

戳气球问题（基础版本）题目描述：给定一组气球，每个气球上标有一个数字。当你戳破一个气球时，你可以获得一定数量的硬币，具体规则是：戳破第i个气球时，你可以获得 nums[left] * nums[i] * nums[right] 枚硬币。这里left和right是与第i个气球相邻的气球的索引。戳破气球i后，气球left和气球right会变成相邻的气球。你的目标是选择戳破气球的顺序，使得获得的硬币总数最大。注意：你可以假设 nums[-1] = nums[n] = 1 ，但它们在数组中并不真实存在，因此不会影响你的戳破操作。 0 ≤ n ≤ 300，其中n是气球的数量。每个气球上的数字在[ 0, 100 ]的范围内。解题过程：问题分析：这个问题看似简单，但戳破一个气球后，数组的相邻关系会改变，这使得直接使用贪心策略（例如每次都戳破数字最小的气球）会失败。我们需要找到一个戳破顺序，使得总收益最大。区间动态规划是解决这类问题的有效方法。关键思路转变：直接思考“先戳破哪个气球”是困难的，因为戳破一个气球后，左右两边的气球会变得相邻，破坏了原有的区间结构。一个更巧妙的思路是：考虑最后一个被戳破的气球。如果我们能确定最后一个被戳破的气球k，那么在戳破k之前，区间 [i, k-1] 和 [k+1, j] 的气球已经被戳破，并且由于k是最后一个被戳破的，此时与k相邻的就是区间边界外的两个“虚拟气球” nums[i-1] 和 nums[j+1] 。因此，戳破k获得的硬币就是 nums[i-1] * nums[k] * nums[j+1] 。定义状态：定义 dp[i][j] 表示戳破区间 [i, j] 内所有气球（注意，区间两端的边界气球 i-1 和 j+1 还没有被戳破）所能获得的最大硬币数。为了处理边界情况，我们可以在原始数组 nums 的首尾各添加一个1，即创建一个新数组 vals ，其中 vals[0] = vals[n+1] = 1 ， vals[1..n] = nums[0..n-1] 。这样，区间 [1, n] 就是我们要处理的所有气球。状态转移方程：对于区间 [i, j] ，我们枚举这个区间内最后一个被戳破的气球k（ i <= k <= j ）。在戳破k之前，区间 [i, k-1] 和 [k+1, j] 内的气球必须已经被戳破。由于k是最后一个被戳破的，此时与k相邻的就是区间 [i, j] 的边界外的两个气球，即 vals[i-1] 和 vals[j+1] 。因此，戳破k获得的硬币是 vals[i-1] * vals[k] * vals[j+1] 。那么，总收益就是：戳破左边区间 [i, k-1] 的最大收益 + 戳破k的收益 + 戳破右边区间 [k+1, j] 的最大收益。状态转移方程为： dp[i][j] = max(dp[i][j], dp[i][k-1] + vals[i-1]*vals[k]*vals[j+1] + dp[k+1][j]) ，其中k从i遍历到j。边界条件与初始化：当区间长度为0（即 i > j ）时， dp[i][j] = 0 ，因为没有气球可戳。当区间长度为1（即 i == j ）时， dp[i][j] = vals[i-1] * vals[i] * vals[i+1] ，因为此时k只能是i，且左右区间均为空。计算顺序：由于计算 dp[i][j] 时需要用到 dp[i][k-1] 和 dp[k+1][j] ，即区间长度更小的子区间的结果，因此我们需要按照区间长度从小到大的顺序进行计算。先计算所有长度为1的区间，然后是长度为2的区间，依此类推，直到长度为n的区间 [1, n] 。最终结果：我们的目标是戳破所有气球，即区间 [1, n] ，因此最终结果为 dp[1][n] 。示例（用于理解）：假设气球数字为[ 3, 1, 5, 8 ]。构建 vals 数组为[ 1, 3, 1, 5, 8, 1 ]（n=4）。我们需要计算 dp[1][4] 。例如，当k=3（即值为5的气球）作为最后一个被戳破时：左边区间[ 1,2]（气球3和1）的最大收益为 dp[1][2] 。右边区间[ 4,4]（气球8）的最大收益为 dp[4][4] 。戳破k=3的收益为 vals[0]*vals[3]*vals[5] = 1*5*1 = 5 。总收益为 dp[1][2] + 5 + dp[4][4] 。我们需要枚举k=1,2,3,4，取最大值作为 dp[1][4] 。通过这种区间动态规划的方法，我们可以系统地计算出所有可能戳破顺序中的最大收益。