(DP动态规划) Leetcode 312. Burst Balloons

第一次做动态规划的题目

题目

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: 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。问该以什么顺序戳气球得到的奖励最大

最笨的思路

枚举法：将所有的情况列举一遍。当有n个气球的时候，第一步我们有n种选择，第二步我们又有n-1个选择......显然全枚举的算法复杂度为 $O(N!)$ ,效率不敢恭维，因此这里就不实现——因为不可能过。

参阅

进一步想法

我们需要去考虑上面枚举法做了什么重复的计算。我们可以想到，给定一组气球，它所能获得的最大的奖励应该和前面已经被戳的气球无关——被戳过的气球只是在求和的时候累积上了而已。

对于给定k<n, 其可能的组合数有 $C_n^k$ 种，我们可以把k(从1开始)的所有情况都记录在内存上，k+1就可以基于k进行计算，那么我们总共需要进行的计算就是
$C_n^1+C_n^2+...+C_n^n$
这种算法优于 $O(N!)$ , 但仍然坏于 $O(2^N)$ ; 我们需要更优的算法

分治的想法

我们考虑用分治去思考这一道题。先是正常地考虑分治，我戳爆某个气球，可不可以把剩下的气球分成两堆呢？这是否可行的前提是两堆会不会互相干扰：答案是肯定的，在戳爆某个气球以后，左堆的最右气球会需要右堆的最左气球来进行计算。

这时候我们需要反向的思维：我们正向地想戳气球的过程，当然会导致两堆相互影响。那如果我们考虑的是在这一堆里最后戳爆的那个气球呢？假如A,B,C,D,E中我最后戳C, 那左堆(A,B)在戳的过程中显然会以C为右边界，而右堆(D,E)以C为左边界——这就实现了分治，两个子问题是相互不干扰的。

想一下为什么分治会更好，它少算了哪些步骤

具体的算法如下：

public int maxCoins(int[] iNums) {
    int[] nums = new int[iNums.length + 2];
    int n = 1;
    for (int x : iNums) if (x > 0) nums[n++] = x;
    nums[0] = nums[n++] = 1;


    int[][] memo = new int[n][n];
    return burst(memo, nums, 0, n - 1);
}

public int burst(int[][] memo, int[] nums, int left, int right) {
    if (left + 1 == right) return 0;
    if (memo[left][right] > 0) return memo[left][right];
    int ans = 0;
    for (int i = left + 1; i < right; ++i)
        ans = Math.max(ans, nums[left] * nums[i] * nums[right] 
        + burst(memo, nums, left, i) + burst(memo, nums, i, right));
    memo[left][right] = ans;
    return ans;
}
// 12 ms

[LeetCode](week12)312. Burst Balloons