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

分析

题意是给定一个数组,每次painted一个ballon,并得到nums[left] * nums[i] * nums[right] 个硬币,让求能得到的最大硬币数是多少。

我们抽象一下这道题的意思,给定一个数组,每次抽取一个数字,并得到一定的值,求该值的最大值

思路1 Top-down

比较直接的想法是暴力法嘛,定义left=0,right=n-1,让i在[left, right]之间进行递归。这个虽然说是暴力法,其实可以理解成将大问题拆解成小问题,同时为了优化时间呢,我们再用一个二维数组memo[m][n]来保存。

分析一下题目,如何拆解呢?对于一个区间而言[left, …, i, …, right],假设i是最后一个被抽取的元素,那么我们得到的最后一个值就是nums[left] * nums[i] * nums[right]。因此我们从最后一次开始,得到如下代码:

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;
}

思路2 Dp

仍然以[3, 1, 5 ,8]为例,因为先吹爆分数为3的气球只能得到两个数相乘的分数,先吹爆分数为5的气球反而更优。但是我们可以知道,对于8而言,先吹3再吹5,和先吹5再吹3,都是一样的,因为8是最后吹。即3和5的问题只在[3, 5]的区间内,跟区间为没有关系,因此我们可以用区间dp去解决这个问题。

dp[i][j]表示吹爆i到j之间的气球所能得到的最大分数。如何转移?那么就穷举先吹爆的气球的编号k,但问题在于,先吹爆气球k会是的k-1号和k+1号气球相邻。此时区间发生了变化。那么可以像石子合并那样反过来。最后吹爆k号气球,那样我们的dp方程就很好定义了。dp[i][j] = dp[i][k-1] + score(k) + dp[k+1][j]。先吹区间[i, k – 1]和区间[k+1, j],最后吹k。

那么我们总结一下dp的四要素:

Definition

dp[i][j]表示吹爆i到j之间的气球所能得到的最大分数

Function

dp[i][j] = max(dp[i][k-1] + score(k) + dp[k+1][j], k属于[i, j]

Initialize

dp[i][i] = 0 for each i

Answer

dp[1][n]

因此得到如下代码:

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;
    newNums[0] = newNums[n++] = 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];
}

小记

对于这种明显存在先后顺序状态的题目,考虑动态规划

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号