LeetCode: 312. Burst Balloons

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. 记：​​record[i][j]​​ 为在原气球序列中，区间 [i, j] 的气球炸裂能得到的最大值
2. 则，​​record[i][j] = max(record[i][k-1] + record[k+1][j] + nums[i-1]*nums[k]*nums[j+1], ...)​​​ 其中 ​​k=i...j​​​ （假设区间 ​​[i, j]​​​ 中最后爆裂的是下标为 ​​k​​ 的气球）
3. 由于第 k 个气球最后一个爆裂，因此其左右的气球互相之间都没有了关系（一直都有它在中间隔开）。

AC 代码

func max(lhv, rhv int) int {
    if lhv > rhv {
        return lhv
    } else {
        return rhv
    }
}
func maxCoinsRef(nums []int, record *[][]int, beg int, end int) int{
    if beg > end || beg < 0 || end >= len(nums) {
        return 0
    } else if (*record)[beg][end] !=  -1 {
        return (*record)[beg][end]
    } else if beg == end {
        burstVal := nums[beg]
        if 0 != beg { 
            burstVal *= nums[beg-1]
        }
        if len(nums)-1 != beg {
            burstVal *= nums[beg+1]
        }
        
        (*record)[beg][end] = burstVal
    } else {
        // [beg, end] 的气球 i 最后 burst
        for i := beg; i <= end; i++ {
            burstVal := nums[i]
            if beg != 0 { 
                burstVal *= nums[beg-1]
            }
            if end != len(nums)-1 {
                burstVal *= nums[end+1]
            }
            
            (*record)[beg][end] = max((*record)[beg][end], 
                maxCoinsRef(nums, record, beg, i-1) + 
                burstVal +  
                maxCoinsRef(nums, record, i+1, end))
        }
    }

    return (*record)[beg][end]
}

func maxCoins(nums []int) int {
    if len(nums)== 0 { return 0 }
    
    // record[i][j]: maxCoins(nums[i,j+1])
    record := make([][]int, len(nums))
    for i := 0; i < len(record); i++ {
        record[i] = make([]int, len(nums))
        
        for j := 0; j < len(record[i]); j++ {
            record[i][j] = -1
        }
    }
    
    maxCoinsRef(nums, &record, 0, len(nums)-1)
    
    return record[0][len(nums)-1]
}