(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个选择......显然全枚举的算法复杂度为,效率不敢恭维，因此这里就不实现——因为不可能过。

参阅

进一步想法

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

对于给定k<n, 其可能的组合数有 种，我们可以把k(从1开始)的所有情况都记录在内存上，k+1就可以基于k进行计算，那么我们总共需要进行的计算就是

这种算法优于, 但仍然坏于; 我们需要更优的算法

分治的想法

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

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

具体的算法如下：

func maxCoins(nums []int) int {
    
    record := []int{1}
    record = append(record, nums...)
    record = append(record, 1)
    
    fmt.Println(record)
    
    return DC(0, len(record)-1, record)
}


// DC: Calculate the max coins got from (leftB, rightB), boundary exclueded
func DC(leftB, rightB int, record []int) int{
    // Go through every possibility of last balloon burst within the boundaries
    
    if leftB + 1 == rightB {
        return 0
    }
    
    max := 0
    for i := leftB + 1; i < rightB; i++ {
        temp := record[leftB] * record[i] * record[rightB] + DC(leftB, i, record) + DC(i, rightB, record)
        if temp > max {
            max = temp
        }
    }
    return max
}

很可惜这个算法超时了

动态规划-更进一步的优化

但是这并不是结束。我们很容易可以发现这里面有大量重复的运算。这时我们不难想到借用动态规划的思想来解决这个问题——将重复的结果保存到内存当中

func maxCoins(nums []int) int {
    
    record := []int{1}
    record = append(record, nums...)
    record = append(record, 1)
    
    fmt.Println(record)
    mem := make([][]int, len(record))
    for i := range(mem){
        mem[i] = make([]int, len(record))
    }
    return DC(0, len(record)-1, record, mem)
}

// DC: Calculate the max coins got from (leftB, rightB), boundary exclueded
func DC(leftB, rightB int, record []int, mem [][]int) int{

    // Go through every possibility of last balloon burst within the boundaries
    if leftB + 1 == rightB {
        return 0
    }
    
    if mem[leftB][rightB] != 0 {
        return mem[leftB][rightB]
    }
    
    max := 0
    for i := leftB + 1; i < rightB; i++ {
        temp := record[leftB] * record[i] * record[rightB] + DC(leftB, i, record, mem) + DC(i, rightB, record, mem)
        if temp > max {
            max = temp
            mem[leftB][rightB] = temp
        }
    }
    return max
}

很遗憾，这份代码也只打败了20%多的代码。

纯粹的动态规划

上面的局部动态规划这么低的KO率怎能够让我们满足呢？通过上面的代码编写，我们很显然发现可以将递归的过程变成循环。

简单来说，就是先将left + 1 == right的值先全部赋为0（由于Go语言的机制默认初始化为0就不用额外操作了）；而后left + 2 == right的值可以根据left + 1 == right的值计算出来；再然后逐渐递增直到算出(0, length+2)即为结果（由于按照题目要求两端都加了1作为墙壁，所以是len+2）。

代码如下：

func maxCoins(nums []int) int {
    
    record := []int{1}
    record = append(record, nums...)
    record = append(record, 1)
    
    fmt.Println(record)
    mem := make([][]int, len(record))
    for i := range(mem){
        mem[i] = make([]int, len(record))
    }
    // mem 全部初始化为 0
    for stretch := 2; stretch < len(record); stretch++ {
        for left := 0; left + stretch < len(record); left++ {
            max := 0
            right := left + stretch
            for i := left + 1; i < left + stretch; i++ {
                temp := record[left] * record[i] * record[right] + mem[left][i] + mem[i][right]
                if temp > max {
                    max = temp
                    mem[left][right] = temp
                }
            }
        } 
    }
    return mem[0][len(record)-1]
}

Runtime: 8 ms, faster than 57.14% of Go online submissions for Burst Balloons.

这样的结果就差强人意了

还能再优化吗

还能再优化。对代码结构可以做进一步的优化

func maxCoins4(nums []int) int {
    
    record := append([]int{1}, nums...)
    record = append(record, 1)
    
    fmt.Println(record)
    mem := make([][]int, len(record))
    for i := range(mem){
        mem[i] = make([]int, len(record))
    }
    // mem 全部初始化为 0
    lens := len(record)
    for stretch := 2; stretch < lens; stretch++ {
        for left := 0; left + stretch < lens; left++ {
            max := 0
            right := left + stretch
            for i := left + 1; i < right; i++ {
                temp := record[left] * record[i] * record[right] + mem[left][i] + mem[i][right]
                if temp > max {
                    max = temp
                    mem[left][right] = temp
                }
            }
        } 
    }
    return mem[0][lens-1]
}

Runtime: 4 ms, faster than 100.00% of Go online submissions for Burst Balloons.

令人满足。