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
1
2

示例 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 right
    for (int i = thisInputIndex + 1; i < numsSize; i++) {
        if (arr[i] != -1) {
            aftervalue = arr[i];
            break;
        }
    }
    
    // Find the first non -1 value on the left
    for (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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

思路分析

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

拆解分析

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

复杂度分析

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

结果

一题多解

动态规划

动态规划思路分析

1. 定义状态：使用二维数组 dp，其中 dp[i][j] 表示戳破 nums[i...j] 区间内所有气球可以获得的最大硬币数量。
2. 状态转移：枚举区间内所有可能的最后一个被戳破的气球 k，计算戳破 k 号气球后的分数贡献，并加上 k 两侧已戳破气球的最大分数贡献。
3. 初始化：所有单个气球戳破后获得的硬币数是 nums[i-1] * nums[i] * nums[i+1]。
4. 结果记录：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]);
            }
        }
    }
1
2
3
4
5
6
7

• 第一层：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

结果

总结

dp相比于dfs暴力枚举所有情况，会大量使用之前得到的值来起到剪枝的效果，对于现在大家不缺空间来说肯定是dp更优，但是如果用在小型嵌入式系统，ram不够的话，dfs+剪枝也是一种可以考虑的方法。