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++实现打气球游戏内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 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(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(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(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(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(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"] 这

  • 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(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]

  • Pygame实战之实现扎气球游戏

    目录 导语 正文 一.准备中 二.代码演示 三.效果展示 导语 ​前几天,有人私信小编: 说陪女朋友在小广场上面逛街玩儿扎气球:结果一个都没扎破,扎心了老铁. 女朋友都要离家出走了~让我给想想办法:小编只想给你一个表情. ​哈哈哈,开玩笑的~于是,为了满足需求,小编做了一个重大决定:熬夜给他做了一款扎气球的小 游戏,可以拿去哄哄女朋友啦~ 这游戏做完之后木子已经替大家玩儿过了,这个很棒,不信的话你自己试试? 正文 本文的扎气球小游戏原型就是路边的扎气球的游戏撒,基于Pygame做的! 就准备好射

  • javascript+css3开发打气球小游戏完整代码

    效果知识点: css3画气球, 自定义属性运用,随机阵列, DOM元素操作,高级回调函数与参数复传,动态布局,鼠标事件,定时器运用,CSS3新增样式等. css代码如下: <style> {margin:0;padding:0;} body{background:#434343;overflow:hidden} .balloon{ position:absolute; left:0; top:0; margin:auto; width:160px; height:160px; 圆角: 左上 右

  • C++实现LeetCode(55.跳跃游戏)

    [LeetCode] 55. Jump Game 跳跃游戏 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach th

  • C++实现LeetCode(45.跳跃游戏之二)

    [LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • JavaScript实现气球打字的小游戏

    目录 一.实现效果 1.定义球的类 二.源码仓库和效果 一.实现效果 1.定义球的类 气球类中我们需要对26个字符进行处理 this.arr = "abcdefghijklmnopqrstuvwxyz".split(""); 生成一个随机字母 this.index = parseInt(Math.random() * this.arr.length); // 定义随机字符 this.str = this.arr[this.index]; 生成一个div标签并对图片进

  • JavaScript实现Fly Bird小游戏

    本教程为大家分享了Fly Bird小游戏的制作流程,供大家参考,具体内容如下 1.分析页面结构,理清需求和功能 游戏有三个界面,分别是开始界面,游戏界面和游戏结束界面. 1.1 开始界面 start.gif 游戏的大背景 上下移动的游戏标题和翅膀摆动的小鸟 start 按钮,点击进入游戏界面 一直移动的地面 1.2 游戏界面 play.gif 显示越过障碍数量的计分器 移动的障碍物,分别是上管道和下管道 点击游戏界面,小鸟向上飞起,然后在重力作用下下坠, 当小鸟和管道碰撞后,结束界面弹出,同时小

  • 基于javascript代码检测访问网页的浏览器呈现引擎、平台、Windows操作系统、移动设备和游戏系统

    废话不多说了,直接给大家贴js代码了,代码附有注释,感兴趣的朋友一起学习吧. /** * Author: laixiangran. * Created by laixiangran on 2015/12/02. * 检测访问网页的浏览器呈现引擎.平台.Windows操作系统.移动设备和游戏系统 * ******************************************************************** * 各版本浏览器在windows10.0下的用户代理字符串:

  • 基于C语言实现的贪吃蛇游戏完整实例代码

    本文以实例的形式讲述了基于C语言实现的贪吃蛇游戏代码,这是一个比较常见的游戏,代码备有比较详细的注释,对于读者理解有一定的帮助. 贪吃蛇完整实现代码如下: #include <graphics.h> #include <conio.h> #include <stdlib.h> #include <dos.h> #define NULL 0 #define UP 18432 #define DOWN 20480 #define LEFT 19200 #defi

随机推荐