【leetcode】312.戳气球 （超详细解析，动态规划）_有 n 个气球,编号为 0 到 n 1,每个气球上都标有一个数字,这些数字存在数组 num

312. 戳气球

难度困难

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

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

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

说明:

• 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

输入: [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
3
4

一、回溯思路

先来顺一下解决这种问题的套路：

我们前文多次强调过，很显然只要涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值。

所以说，只要遇到求最值的算法问题，首先要思考的就是：如何穷举出所有可能的结果？

穷举主要有两种算法，就是回溯算法和动态规划，前者就是暴力穷举，而后者是根据状态转移方程推导「状态」。

如何将我们的扎气球问题转化成回溯算法呢？这个应该不难想到的，我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的那个找出来，对吧。

那么，这不就是一个「全排列」问题嘛。其实只要稍微改一下逻辑即可，伪码思路如下：

int res = Integer.MIN_VALUE;
/* 输入一组气球，返回戳破它们获得的最大分数 */
int maxCoins(int[] nums) {
   
    backtrack(nums, 0); 
    return res;
}
/* 回溯算法的伪码解法 */
void backtrack(int[] nums, int socre) {
   
    if (nums 为空) {
   
        res = max(res, score);
        return;
    }
    for (int i = 0; i < nums.length; i++) {
   
        int point = nums[i-1] * nums[i] * nums[i+1];
        int temp = nums[i];
        // 做选择
        在 nums 中删除元素 nums[i]
        // 递归回溯
        backtrack(nums, score + point);
        // 撤销选择
        将 temp 还原到 nums[</
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24