LeetCode312 戳气球_312戳气球回溯法

回溯思想

很显然涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值

所以说，只要遇到求最值的问题，首先要思考的就是：如何穷举所有可能的结果
穷举主要有两种算法：就是回溯算法和动态规划，前者就是暴力穷举,而后者是根据状态转移方程推导状态
如何将我们的扎气球问题转化为回溯算法呢？这个应该不难想到的，我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的找出来吧
那么，这不就是一个[全排列]问题吗？

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[i]
    }
}

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

回溯算法就是这么简单粗暴，但是相应的，算法的效率非常低。这个解法等同于全排列，所以时间复杂度是阶乘级别的，非常高，题目说

动态规划思路

这个动态规划问题和我们之前的动态规划系列文章相比有什么特别之处？为什么它比较难呢？

原因在于，这个问题中我们每戳破一个气球 nums[i]，得到的分数和该气球相邻的气球 nums[i-1] 和 nums[i+1] 是有相关性的。

我们前文动态规划套路框架详解 说过运用动态规划算法的一个重要条件：子问题必须独立。所以对于这个戳气球问题，如果想用动态规划，必须巧妙地定义 dp 数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。

如何定义 dp 数组呢，这里需要对问题进行一个简单地转化。题目说可以认为 nums[-1] = nums[n] = 1，那么我们先直接把这两个边界加进去，形成一个新的数组 points：

int maxCoins(int[] nums) {
    int n = nums.length;
    // 两端加入两个虚拟气球
    int[] points = new int[n + 2];
    points[0] = points[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        points[i] = nums[i - 1];
    }
    // ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13

那么，对于一组给定的 i 和 j，我们只要穷举 i < k < j 的所有气球 k，选择得分最高的作为 dp[i][j] 的值即可，这也就是状态转移方程：

// 最后戳破的气球是哪个？
for (int k = i + 1; k < j; k++) {
    // 择优做选择，使得 dp[i][j] 最大
    dp[i][j] = Math.max(
        dp[i][j], 
        dp[i][k] + dp[k][j] + points[i]*points[j]*points[k]
    );
}

1
2
3
4
5
6
7
8
9

关于「状态」的穷举，最重要的一点就是：状态转移所依赖的状态必须被提前计算出来。

package com.zj.FDynamicProgramming.taolu;

/**
 * @Author Zhou Jian
 * @Date 2020/8/10
 */
public class Problem312 {

    /**
     * dp[i] 前i个气球戳完所获得的最大硬币数
     *
     * dp[i][j] = x 戳破气球i和气球j之间（开区间，不包括i和j）的所有气球，可以获得的最高分数为x
     * 那么根据这个定义，题目要求的结果就是dp[0][n+1]的值，而baseCase就是dp[i][j]=0
     *  dp[i][j] nums{i,j}区间戳破气球的最大值
     *              max(dp[i][j],dp[i][k]+dp[k][j]+points[k])   (i<k<j)
     *
     *              不就是想求戳破气球 i 和气球 j 之间的最高分数吗，如果「正向思考」，就只能写出前文的回溯算法；我们需要「反向思考」，想一想气球 i 和气球 j 之间最后一个被戳破的气球可能是哪一个？
     *
     * 其实气球 i 和气球 j 之间的所有气球都可能是最后被戳破的那一个，不防假设为 k。回顾动态规划的套路，这里其实已经找到了「状态」和「选择」：i 和 j 就是两个「状态」，最后戳破的那个气球 k 就是「选择」。
     *
     * 作者：labuladong
     * 链接：https://leetcode-cn.com/problems/burst-balloons/solution/dong-tai-gui-hua-tao-lu-jie-jue-chuo-qi-qiu-wen-ti/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     *
     * 关键在于 dp 数组的定义，需要避免子问题互相影响，
     * 所以我们反向思考，将 dp[i][j] 的定义设为开区间
     * 考虑最后戳破的气球是哪一个，以此构建了状态转移方程。
     */
    public int maxCoins(int[] nums) {

        int n = nums.length;
        //添加两侧虚拟气球
        int[] points = new int[n+2];
        points[0] =points[n+1]=1;

        for(int i=1;i<=n;i++) points[i]=nums[i-1];

        //baseCase被初始化为0
        int[][] dp = new int[n+2][n+2];
        // 开始状态转移
        // i应该从下往上
        for(int i=n;i>=0;i--){
            // j应该从左往右
            for(int j=i+1;j<n+2;j++){
                // 最后戳破的气球是哪个？
                for(int k=i+1;k<j;k++){
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k]+dp[k][j]+points[i]*points[j]*points[k]
                    );
                }
            }
        }
        return dp[0][n+1];
    }
}


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