C++实现LeetCode(312.打气球游戏)

[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 iyou 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

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

这道题提出了一种打气球的游戏,每个气球都对应着一个数字,每次打爆一个气球,得到的金币数是被打爆的气球的数字和其两边的气球上的数字相乘,如果旁边没有气球了,则按1算,以此类推,求能得到的最多金币数。参见题目中给的例子,题意并不难理解。那么大家拿到题后,总是会习惯的先去想一下暴力破解法吧,这道题的暴力搜索将相当的复杂,因为每打爆一个气球,断开的地方又重新挨上,所有剩下的气球又要重新遍历,这使得分治法不能 work,整个的时间复杂度会相当的高,不要指望可以通过 OJ。而对于像这种求极值问题,一般都要考虑用动态规划 Dynamic Programming 来做,维护一个二维动态数组 dp,其中 dp[i][j] 表示打爆区间 [i,j] 中的所有气球能得到的最多金币。题目中说明了边界情况,当气球周围没有气球的时候,旁边的数字按1算,这样可以在原数组两边各填充一个1,方便于计算。这道题的最难点就是找状态转移方程,还是从定义式来看,假如区间只有一个数,比如 dp[i][i],那么计算起来就很简单,直接乘以周围两个数字即可更新。如果区间里有两个数字,就要算两次了,先打破第一个再打破了第二个,或者先打破第二个再打破第一个,比较两种情况,其中较大值就是该区间的 dp 值。假如区间有三个数呢,比如 dp[1][3],怎么更新呢?如果先打破第一个,剩下两个怎么办呢,难道还要分别再遍历算一下吗?这样跟暴力搜索的方法有啥区别呢,还要 dp 数组有啥意思。所谓的状态转移,就是假设已知了其他状态,来推导现在的状态,现在是想知道 dp[1][3] 的值,那么如果先打破了气球1,剩下了气球2和3,若之前已经计算了 dp[2][3] 的话,就可以使用其来更新 dp[1][3] 了,就是打破气球1的得分加上 dp[2][3]。那假如先打破气球2呢,只要之前计算了 dp[1][1] 和 dp[3][3],那么三者加起来就可以更新 dp[1][3]。同理,先打破气球3,就用其得分加上 dp[1][2] 来更新 dp[1][3]。说到这里,是不是感觉豁然开朗了 ^.^

那么对于有很多数的区间 [i, j],如何来更新呢?现在是想知道 dp[i][j] 的值,这个区间可能比较大,但是如果知道了所有的小区间的 dp 值,然后聚沙成塔,逐步的就能推出大区间的 dp 值了。还是要遍历这个区间内的每个气球,就用k来遍历吧,k在区间 [i, j] 中,假如第k个气球最后被打爆,那么此时区间 [i, j] 被分成了三部分,[i, k-1],[k],和 [k+1, j],只要之前更新过了 [i, k-1] 和 [k+1, j] 这两个子区间的 dp 值,可以直接用 dp[i][k-1] 和 dp[k+1][j],那么最后被打爆的第k个气球的得分该怎么算呢,你可能会下意识的说,就乘以周围两个气球被 nums[k-1] * nums[k] * nums[k+1],但其实这样是错误的,为啥呢?dp[i][k-1] 的意义是什么呢,是打爆区间 [i, k-1] 内所有的气球后的最大得分,此时第 k-1 个气球已经不能用了,同理,第 k+1 个气球也不能用了,相当于区间 [i, j] 中除了第k个气球,其他的已经爆了,那么周围的气球只能是第 i-1 个,和第 j+1 个了,所以得分应为 nums[i-1] * nums[k] * nums[j+1],分析到这里,状态转移方程应该已经跃然纸上了吧,如下所示:

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 )

有了状态转移方程了,就可以写代码,下面就遇到本题的第二大难点了,区间的遍历顺序。一般来说,遍历所有子区间的顺序都是i从0到n,然后j从i到n,然后得到的 [i, j] 就是子区间。但是这道题用这种遍历顺序就不对,在前面的分析中已经说了,这里需要先更新完所有的小区间,然后才能去更新大区间,而用这种一般的遍历子区间的顺序,会在更新完所有小区间之前就更新了大区间,从而不一定能算出正确的dp值,比如拿题目中的那个例子 [3, 1, 5, 8] 来说,一般的遍历顺序是:

[3] -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] -> [1] -> [1, 5] -> [1, 5, 8] -> [5] -> [5, 8] -> [8] 

显然不是我们需要的遍历顺序,正确的顺序应该是先遍历完所有长度为1的区间,再是长度为2的区间,再依次累加长度,直到最后才遍历整个区间:

[3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]

这里其实只是更新了 dp 数组的右上三角区域,最终要返回的值存在 dp[1][n] 中,其中n是两端添加1之前数组 nums 的个数。参见代码如下:

解法一:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int len = 1; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1;
                for (int k = i; k <= 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]);
                }
            }
        }
        return dp[1][n];
    }
};

对于题目中的例子[3, 1, 5, 8],得到的dp数组如下:

0    0    0    0       0     0
0    3    30  159  167  0
0    0    15  135  159  0
0    0    0    40     48   0
0    0    0    0       40   0
0    0    0    0       0     0

这题还有递归解法,思路都一样,就是写法略有不同,参见代码如下:

解法二:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        return burst(nums, dp, 1 , n);
    }
    int burst(vector<int>& nums, vector<vector<int>>& dp, int i, int j) {
        if (i > j) return 0;
        if (dp[i][j] > 0) return dp[i][j];
        int res = 0;
        for (int k = i; k <= j; ++k) {
            res = max(res, nums[i - 1] * nums[k] * nums[j + 1] + burst(nums, dp, i, k - 1) + burst(nums, dp, k + 1, j));
        }
        dp[i][j] = res;
        return res;
    }
};

到此这篇关于C++实现LeetCode(312.打气球游戏)的文章就介绍到这了,更多相关C++实现打气球游戏内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-18

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

C++实现LeetCode(91.解码方法)

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

C++实现LeetCode(136.单独的数字)

[LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

C++实现LeetCode(187.求重复的DNA序列)

[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

C++实现LeetCode(86.划分链表)

[LeetCode] 86.Partition List 划分链表 Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions

C++实现LeetCode(89.格雷码)

[LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

C++实现LeetCode(87.搅乱字符串)

[LeetCode] 87. Scramble String 搅乱字符串 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great":     great /    \ gr    eat / \    /  \

C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

Java实现复原IP地址的方法

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式. 示例: 输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"] PS: 跪了,得LeetCode者得天下,上次我学的位运算符,这次学的ip地址 class Solution { private List<String> res = new ArrayList<>(); public List&

python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意 给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&

SunTB编写IP地址设置切换批处理

修正一个提取网络连接名称的错误,原因在于之前在FOR中使用空格作为分隔符 如果网络连接名为"本地连接 2",原来只会识别成"本地连接",从而导致设置失败 现已更正 说明:1.可以选择要设置的网络连接 2.可以手动设定固定IP,也可以通过DHCP自动获取 3.可以在批处理中预设多组MAC与IP对应数据,当内网有MAC绑定时可快速查询相应IP 4.DNS设置提供四类数据(中国电信. 中国联通/中国网通.中国移动/ 国铁通.内网网关) DNS为福州地区数据,请自行更改为当

IP地址正则表达式匹配方法

正则表达式(Regular Expression,在代码中常简写为regex.regexp或RE)是计算机科学的一个概念.正则表达式使用单个字符串来描述.匹配一系列符合某个句法规则的字符串.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本.许多程序设计语言都支持利用正则表达式进行字符串操作.在很多文本编辑器里,正则表达式通常被用来检索.替换那些符合某个模式的文本. 正则表达式 ^(25[0-5]|2[0-4][0-9]|[0-1]{1}[0-9]{2}|[1-9]{1}[

最全正则表达式总结:验证QQ号、手机号、Email、中文、邮编、身份证、IP地址等

什么是 RegExp? RegExp 是正则表达式(Regular expression)的缩写,作用是对字符串执行模式匹配. 通常用于格式验证.正则替换.查找子串等 各种编程语言的正则表达式基本相同,不同的语言可能会有一些细小的差别 RegExp 语法 1.// 直接实例化 2.var reg = new RegExp(pattern [, flags]) 3.// 隐式创建(推荐) 4.var reg = /pattern/flags; 参数 pattern 是一个字符串,指定了正则表达式的

使用CDN之后APACHE日志记录中IP地址不正确的解决方案

最近在搞APACHE日志分析,装好了awstats之后,这两天进行了观察, 报表日期 月 1 月 2010 首次参观日期 2010年01月12日 11:04 最近参观日期 2010年01月13日 23:59     参观者 参观人次 网页数 文件数 字节 浏览器流量 * 77  226  (2.93 参观人次/参观者) 508979 (2252.11 网页数/参观) 509492 (2254.38 文件数/参观) 13.67 G字节 (63430.28 K字节/参观) 非浏览器流量 *  117

Google打不开的解决方法和IP地址表

本文将给出一些能够正常访问被屏蔽的Google搜索引擎的常用方法以及Google的IP地址表. 在Google.com里面进行搜索的时候,经常会遇到突然出现"该页无法显示"的提示,并且之后的十多分钟都无法正常连接Google,这里给出一些方法,可以解决大部分Google无法访问或进不去的问题. 1.如果是搜索过程中出现"该页无法显示"的提示,接着就无法访问Google,那么对于ADSL用户,可以尝试断开网络连接,然后重新拨号上网,这样你的IP地址就发生了变化,这时候

为VMware的多台虚拟机绑定IP地址的方法

最近我在VMware上面用三台虚拟机搭建了一个hadoop的集群.但是后来发现了一个问题:每次重新打开三台机器的时候,因为主机所连接的网络的变化,会导致VMware中的这三台虚拟机的IP地址也变掉.这会导致ssh失败,三台机器无法通讯.所以总结了一种方式来绑定虚拟机的IP地址. 1.打开虚拟机后,在编辑>模拟网络编辑器>NET设置中查看自己的IP地址.子网掩码.和网关. 2.开启虚拟机服务 我的电脑--> 管理 -->服务和应用程序-->服务 (这个一般情况下我们的电脑都已经

命令行实现MAC与IP地址绑定 ip mac绑定 如何绑定mac地址

为什么要绑定IP呢?你指定的IP能上外网不就可以了吗?之所以要绑定IP,是因为他会会改IP.比如我本机上的IP是192.168.1.11此IP已经在防火墙上面做了设定不可以上网,但我要是知道有一个IP是192.168.1.30的IP能上网,那我不会改把192.168.1.11换成192.168.1.30就可以上网了吗?所以绑定IP就是为了防止他改IP. 因为网卡的MAC地址是全球唯一的跟我们的身份证一样,他一但改了,就不认了.那如何绑定呢? 例如我的IP是192.168.1.11,网卡的MAC地

java获取ip地址示例

如果使用了反向代理软件,将http://192.168.1.110:2046/ 的URL反向代理为http://www.xxx.com/ 的URL时,用request.getRemoteAddr()方法获取的IP地址是:127.0.0.1 或 192.168.1.110,而并不是客户端的真实IP. 经过代理以后,由于在客户端和服务之间增加了中间层,因此服务器无法直接拿到客户端的IP,服务器端应用也无法直接通过转发请求的地址返回给客户端.但是在转发请求的HTTP头信息中,增加了X-FORWARDE