LeetCode312：戳气球

要求

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

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

思路

只要涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值。
穷举主要有两种算法，就是回溯算法和动态规划，前者就是暴力穷举，而后者是根据状态转移方程推导「状态」

方法一：回溯算法
我们其实就是想穷举戳气球的顺序，不同的戳气球顺序可能得到不同的分数，我们需要把所有可能的分数中最高的那个找出来

class Solution {  //O(n!) 超时
    public int maxCoins(int[] nums) {
        int[] state = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            state[i] = 0;
        }
        tryGetCoins(nums,state,0);
        return max;
    }

    int max = 0;
    void tryGetCoins(int[] nums, int[] state,int current){
        int[] tempState = state.clone();
        int i = 0;
        if(finished(state)){
            max = Math.max(max,current);
            return;
        }
        for(i=0;i<nums.length;i++){
            if(state[i] == 1)
                continue;
            tempState[i] = 1;
            tryGetCoins(nums,tempState,current+getCoinsAt(nums,state,i));
            copyArray(tempState,state);
        }
    }
    int getCoinsAt(int[] nums,int[] state,int i){
        int j = 0,result = nums[i];
        for(j = i-1;j>-1;j--){
            if(state[j] == 0){
                result *= nums[j];
                break;
            }
        }
        for(j = i+1;j<state.length;j++){
            if(state[j] == 0){
                result *= nums[j];
                break;
            }
        }
        return result;
    }
    void copyArray(int[] dest,int[] origin){
        for(int i = 0; i<dest.length;i++){
            dest[i] = origin[i];
        }
    }
    boolean finished(int[] state){
        boolean finished = true;
        for(int i = 0; i < state.length;i++){
            if(state[i] == 0)
                finished = false;
        }
        return  finished;
    }
}
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

当我们回溯完所有的戳法之后，就能找出最大得分。但是该回溯法的时间复杂度显然为O(n!)，而气球个数的取值为[0,500]，必然会有超时的问题。

方法二：动态规划
我们每戳破一个气球 nums[i]，得到的分数和该气球相邻的气球 nums[i-1] 和 nums[i+1] 是有相关性的。但运用动态规划算法的一个重要条件：子问题必须独立。所以必须巧妙地定义 dp 数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。
数组两端加入新的虚拟气球，形成一个新的数组 points，现在气球的索引变成了从 1 到 n，points[0] 和 points[n+1] 可以认为是两个「虚拟气球」

状态定义：dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（不包括 i 和 j）的所有气球，获得的最高分数为 x。 base case 就是 dp[i][j] = 0，其中 0 <= i <= n+1, j <= i+1，开区间 (i, j) 中间没有气球可以戳。

// base case 已经都被初始化为 0
int[][] dp = new int[n + 2][n + 2];

---

推导状态转移方程：
假设 k 是气球 i 和气球 j 之间的所有气球最后被戳破的那一个，需要先把开区间 (i, k) 的气球都戳破，再把开区间 (k, j) 的气球都戳破；最后剩下的气球 k，相邻的就是气球 i 和气球 j，这时候戳破 k 的话得到的分数就是 points[i]*points[k]*points[j]。
dp[i][j] 的值应该为：dp[i][k] + dp[k][j] + points[i]*points[k]*points[j]

由于是开区间，dp[i][k] 和 dp[k][j] 不会影响气球 k；而戳破气球 k 时，旁边相邻的就是气球 i 和气球 j 了，最后还会剩下气球 i 和气球 j，这也恰好满足了 dp 数组开区间的定义。
对于一组给定的 i 和 j，我们只要穷举 i < k < j 的所有气球 k，选择得分最高的作为 dp[i][j] 的值即可
dp[i][j] 所依赖的状态是 dp[i][k] 和 dp[k][j]，那么我们必须保证：在计算 dp[i][j] 时，dp[i][k] 和 dp[k][j] 已经被计算出来了（其中 i < k < j）。

选择从下往上遍历

public class LeetCode312 {
    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];
        }
        //base case初始化为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