文档章节

打破气球所能获得的最大积分 Burst Balloons

叶枫啦啦
 叶枫啦啦
发布于 2017/12/22 15:17
字数 684
阅读 5
收藏 0

问题:

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: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

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

解决:

【题意】给定n个气球。每次你可以打破一个,打破第i个,那么你会获得nums[left] * nums[i] * nums[right]个积分。 (nums[-1] = nums[n] = 1)求你可以获得的最大积分数。

① https://segmentfault.com/a/1190000007297715

动态规划。dp[i][j]表示打爆区间[i,j]中的所有气球能得到的最多金币。DP的思想是bottom up

最后的剩下一个气球为i的时候,可以获得的分数为:nums[-1]*nums[i]*nums[n].

那么介于i , j之间的k,有: 

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 ),O(N^2), O(N^2)

class Solution { //15ms
    public static int maxCoins(int[] nums) {
        int[] tmpnums = new int[nums.length + 2];
        System.arraycopy(nums,0,tmpnums,1,nums.length);
        tmpnums[0] = 1;
        int len = tmpnums.length;
        tmpnums[len - 1] = 1;
        int[][] dp = new int[len][len];
        for (int l = 2;l < len;l ++){
            for (int i = 0;i < len - l;i ++){
                int j = i + l;
                for (int k = i + 1;k < j;k ++){
                    dp[i][j] = Math.max(dp[i][j],tmpnums[i] * tmpnums[k] * tmpnums[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][len - 1];
    }
}

② D&C + Memorization,O(N^3) , O(N^2)

memorization是from top to bottom,每一次都将值分成两部分,然后分别计算。对于在left和right中间的位置i,考虑[left,i]和[i,right]能组成的部分,分别对这两部分进行递归求值。用二维数组记录已经计算过的值,避免重复计算。

class Solution { //10ms
    public static int maxCoins(int[] nums) {
        int[] tmpnums = new int[nums.length + 2];
        for (int i = 1;i <= nums.length;i ++){
            tmpnums[i] = nums[i - 1];
        }
        tmpnums[0] = 1;
        tmpnums[tmpnums.length - 1] = 1;
        int len = tmpnums.length;
        int[][] memo = new int[len][len];
        return burst(tmpnums,0,len - 1,memo);
    }
    public static int burst(int[] nums,int i,int j,int[][] memo){
        if (i + 1 == j) return 0;//[i,j]之间没有ballon可以炸掉
        if (memo[i][j] > 0){//如果已经计算过了,则直接返回
            return memo[i][j];
        }
        int res = 0;
        for (int k = i + 1;k < j;k ++){
            res = Math.max(res,nums[i] * nums[k] * nums[j] + burst(nums,i,k,memo) + burst(nums,k,j,memo));//递归获取左右窗口的最大值
        }
        memo[i][j] = res;
        return res;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 12
博文 577
码字总数 384162
作品 0
海淀
私信 提问
[LeetCode] Minimum Number of Arrows to Burst Balloons 最少数量的箭引爆气球

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it'......

机器的心脏
2017/12/12
0
0
leetcode 452. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it'......

努力的C
2017/09/30
0
0
ZOJ Problem Set - 2104 Let the Balloon Rise(map)

Let the Balloon Rise Time Limit: 2 Seconds Memory Limit: 65536 KB Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' fa......

hushhw
2017/11/27
0
0
[Develop Game] AS3 Click the Balloons

与往常一样,打算如何在游戏是要表现你开始编写任何代码之前! 首先,我们需要一个启动按钮。 我们希望有一个新的气球,每5秒。 每个气球应开始于页面的底部,并移动到页面的顶部。 如果气球...

MrLovelyCbb
2014/03/24
0
0
例程:让HelpBalloons飘在你的GSP上空!

在进行网页开发的时候,常常需要显示提示或者帮助信息,实现方法有很多种。这里介绍一种简单易用的Gails插件--HelpBalloon。可以把这个可爱的气球放在GSP的任何地方。 要使用HelpBalloon,请...

groovyland
2010/03/15
107
0

没有更多内容

加载失败,请刷新页面

加载更多

Quartz原理解析

Quartz原理解析 最近项目中好多地方都需要用到定时器,一开始用的是netty的hashWheel,后来发现删除任务的时候不是很好删除,于是就放弃了,然后选择了Quartz。 hashWheel定时器和Quartz的区...

石日天
46分钟前
1
0
explain详解

EXPLAIN列的解释 table 显示这一行的数据是关于哪张表的 type 这是重要的列,显示连接使用了何种类型。从最好到最差的连接类型为 const(读常量,最多只会有一条记录匹配,由于是常量,实际上...

周慕云
50分钟前
1
0
Oracle 修改或新增数据后查不到数据

修改或新增数据后数据库中SQL能查到但执行程序却查不到 因为AutoCommit is OFF 所以 每次新增或修改数据后都要commit 一下,不然只是post edit 的话,执行程序能查到的只是未更新的数据。...

南风末
今天
4
0
python学习整理(1)

#!/usr/bin/env python # -*- conding:utf-8 -*- 1、 python运算: + - * / % ** // In [21]: print(int(1.2)+3) 4 In [22]: print(float(1.2)+3) 4.2 In [15]: print(11//5) 2 In [16]: prin......

芬野de博客
今天
3
0
maven 在无法连接仓库的单机环境下打包程序

前提:依赖的jar已经在本机。 方法:以ojdbc6-11.2.0.4.jar 为例,进入.m2\repository\com\oracle\jdbc\ojdbc6\11.2.0.4 目录,编辑_remote.repositories文件,改写如下: ojdbc6-11.2.0.4....

jingshishengxu
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部