312. 戳气球

题目

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

输入：nums = [3,1,5,8]
输出：167
解释：

nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

输入：nums = [1,5]
输出：10

提示：

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

代码

完整代码

#include <stdio.h>
#include <stdlib.h>#define MAX(a,b) ((a) > (b) ? (a) : (b))typedef struct {int val;int oldindex;
} st_t;int cmp(const void *a, const void *b) {return (*(st_t*)b).val - (*(st_t*)a).val;
}int calcscore(int* arr, int thisInputIndex, int thisInputVal, int numsSize) {int beforevalue = 1;int aftervalue = 1;// Find the first non -1 value on the rightfor (int i = thisInputIndex + 1; i < numsSize; i++) {if (arr[i] != -1) {aftervalue = arr[i];break;}}// Find the first non -1 value on the leftfor (int i = thisInputIndex - 1; i >= 0; i--) {if (arr[i] != -1) {beforevalue = arr[i];break;}}arr[thisInputIndex] = thisInputVal;return thisInputVal * beforevalue * aftervalue;
}void dfs(int* arr, int* nums, int numsSize, int* score, int* highestScore) {int found = 0;for (int i = 0; i < numsSize; i++) {if (arr[i] == -1) {found = 1;int nowscore = calcscore(arr, i, nums[i], numsSize);*score += nowscore;dfs(arr, nums, numsSize, score, highestScore);*score -= nowscore;arr[i] = -1; // Reset the position after recursion}}if (!found && *score > *highestScore) {*highestScore = *score;}
}int maxCoins(int* nums, int numsSize) {int score = 0;int highestScore = 0;int* arr = (int*)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++) {arr[i] = -1; // 初始化为-1，表示该位置还没有填入数字}dfs(arr, nums, numsSize, &score, &highestScore);free(arr);return highestScore;
}

思路分析

回溯算法：通过深度优先搜索（DFS）来枚举所有可能的戳气球顺序，计算每种顺序下能获得的最大硬币数量。
计算分数：定义 calcscore 函数来计算戳破当前气球时可以获得的硬币数，考虑到边界条件处理。
记录最高分：在 DFS 过程中记录获得的最高硬币数。

拆解分析

回溯搜索：遍历数组，每次选取一个未被戳破的气球进行递归处理。
分数计算：计算每次戳破气球后的硬币数，并在递归返回时进行回溯。
结束条件：当所有气球都被戳破时，更新最高硬币数。

复杂度分析

时间复杂度：O(n!)，其中 n 是数组 nums 的长度。每次递归都要对剩余未戳破的气球进行选择，因此是一个阶乘级别的复杂度。
空间复杂度：O(n)，递归栈的深度最大为数组 nums 的长度。

结果

在这里插入图片描述

一题多解

动态规划

动态规划思路分析

定义状态：使用二维数组 dp，其中 dp[i][j] 表示戳破 nums[i...j] 区间内所有气球可以获得的最大硬币数量。
状态转移：枚举区间内所有可能的最后一个被戳破的气球 k，计算戳破 k 号气球后的分数贡献，并加上 k 两侧已戳破气球的最大分数贡献。
初始化：所有单个气球戳破后获得的硬币数是 nums[i-1] * nums[i] * nums[i+1]。
结果记录：dp[0][n-1] 即为所求的最大硬币数。

动态规划拆解分析

最重要的就是这个三重循环：

    for (int length = 2; length < n; length++) {for (int left = 0, right = left + length; left < n - length; left++) {for (int i = left + 1; i < right; i++) {dp[left][right] = MAX(dp[left][right], newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);}}}

第一层：for (int length = 2; length < n; length++)
作用为控制区间长度，因为最终我们需要获得从0 ~ numsSize这个区间的最大值，因此我们需要依次获取长度为 numsSize, numsSize -1, ……, 2,之所以从2开始是因为如果len = 1，不用算，score就是nums[i];
第二层for (int left = 0, right = left + length; left < n - length; left++)：
控制左右边界，从0开始依次扫描一遍各个可能的区间，计算每个可能的区间的得分。
第三层for (int i = left + 1; i < right; i++)：
在区间内戳破每个气球，看看这个区间内戳破哪个气球使得总得分最高，其中，dp[left][i] 和dp[i][right]是戳破从左到i和从i到右的所有气球的分数，这样就保证了第三层循环内戳破第i个气球时，所有其他气球都被戳破并积分。

动态规划复杂度分析

时间复杂度：O(n^3)，三重循环枚举所有可能的区间和最后一个戳破的气球。
空间复杂度：O(n^2)，使用二维数组存储 dp 值。

动态规划代码

#include <stdio.h>
#include <stdlib.h>
#define MAX(a,b) ((a) > (b) ? (a) : (b))int maxCoins(int* nums, int numsSize) {int n = numsSize + 2;int* newNums = (int*)malloc(n * sizeof(int));newNums[0] = newNums[n - 1] = 1;for (int i = 0; i < numsSize; i++) {newNums[i + 1] = nums[i];}int** dp = (int**)malloc(n * sizeof(int*));for (int i = 0; i < n; i++) {dp[i] = (int*)calloc(n, sizeof(int));}for (int length = 2; length < n; length++) {for (int left = 0, right = left + length; left < n - length; left++) {for (int i = left + 1; i < right; i++) {dp[left][right] = MAX(dp[left][right], newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);}}}int result = dp[0][n - 1];for (int i = 0; i < n; i++) {free(dp[i]);}free(dp);free(newNums);return result;
}

结果