GuilinDev

Lc0312

05 August 2008

312 - Burst Balloons

原题概述

Given 

1

n
balloons, indexed from 
1

0
to 
1

n-1
. Each balloon is painted with a number on it represented by array 
1

nums
. You are asked to burst all the balloons. If the you burst balloon 
1

i
you will get 
1

nums[left] * nums[i] * nums[right]
coins. Here 
1

left
and 
1

right
are adjacent indices of 
1

i
. After the burst, the 
1

left
and 
1

right
then becomes adjacent.

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

Note:

  • You may imagine 
    1

    nums[-1] = nums[n] = 1
    . They are not real therefore you can not burst them.
  • 0 ≤ 
    1

    n
    ≤ 500, 0 ≤ 
    1

    nums[i]
    ≤ 100

Example:

1
2
3
4

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算，以此类推，求能得到的最多金币数。又是求极值，那自然用DP，维护一个二维动态数组dp，其中dp[i][j]表示区间[i,j]中的打爆所有气球能得到的最多金币。题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样可以在区间[i,j]两边各填充一个1，递归式：

1
2

dp[i][j] = max(dp[i][j], nums[i - 1]*nums[k]*nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]) 
其中i ≤ k ≤ j

因为每次气球打爆后就不计算了，所以只是更新了dp这个二维数组的右上三角区域（左下三角区域为空），我们最终要返回的值存在dp[0][n-1]中，其中n是两端添加1之前数组nums的个数。

更加详细的解释 https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

代码

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

class Solution {
    public int maxCoins(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        int n = 1;
        for (int x : nums) {
            if (x > 0) {
                newNums[n] = x;
                n++;
            }
        }
        newNums[0] = newNums[n++] = 1;//两边各加一个1，注意这里末尾的元素赋值为1后再自增一下

        int[][] dp = new int[n][n];
        for (int k = 2; k < n; k++) {
            for (int left = 0; left < n - k; left++) {
                int right = left + k;
                for (int i = left + 1; i < right; i++) {
                    dp[left][right] = Math.max(dp[left][right],
                            newNums[left]*newNums[i]*newNums[right] + dp[left][i] + dp[i][right]);
                }
            }
        }
        return dp[0][n-1];
    }
}
This site is open source. Improve this page.