本文主要是介绍LintCode 吹气球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。
样例
给出 [4, 1, 5, 10]
返回 270
nums = [4, 1, 5, 10] burst 1, 得分 4 * 1 * 5 = 20
nums = [4, 5, 10] burst 5, 得分 4 * 5 * 10 = 200
nums = [4, 10] burst 4, 得分 1 * 4 * 10 = 40
nums = [10] burst 10, 得分 1 * 10 * 1 = 10
总共的分数为 20 + 200 + 40 + 10 = 270
动态规划。
首先按照题意，我们可以先在nums数组两端各加一个1，方便计算。
dp[i , j]表示吹爆第i个到第j个气球能获得的最多的分数。对于第i 到 第j个气球中，可以首先吹爆任意一个气球k（i<=k<=j），吹爆第k个气球时，能获得的分数为nums[k]* （此刻k的前一个数）* （此刻k的后一个数），但是由于并不知道之前k左边和右边的气球有没有被吹爆，所以不能确定此刻左右的数。换一种思路，既然可以首先吹爆任意一个气球k，那么也可以选择最后吹爆任意一个气球k。此时，k的左右数字就确定了，分别是nums[i-1]和nums[j+1]。
那么获得的分数就是nums[i-1]* nums[k]* nums[j+1]，这是吹爆k获得的分数，再加上吹爆k之前获得的最大分数dp[i , k-1]+dp[k+1 , j]（即在k之前吹爆的：k左边第i个到第k-1个，k右边第k+1个到第j个）。综上，dp[i , j]=max(nums[i-1]* nums[k]* nums[j+1] + dp[i , k-1]+ dp[k+1 , j])，（对于所有的 k : i<=k<=j）.
显然，求dp[i , j]时，需要dp[i , k-1] , dp[k+1 , j]，即区间长度小于i到j的区间长度的dp。所以可以从区间长度为1开始求解。这个和算法导论上动态规划那一章的矩阵链乘法类似，LintCode上另外一道题 Guess Number Game II也是这种按区间长度的增长来求解。
最后的结果为 dp[1 , n]。
代码如下：
class Solution(object):"""@param {int[]} nums a list of integer@return {int} an integer, maximum coins"""def maxCoins(self, nums):# Write your code heren=len(nums)nums.append(1)nums.insert(0,1)dp=[[0 for x in range(n+2)] for y in range(n+2)]for length in range(1,n+1):for i in range(1,n-length+2):j=i+length-1q=0for k in range(i,j+1):q=nums[i-1]*nums[k]*nums[j+1]+dp[i][k-1]+dp[k+1][j]if q>dp[i][j]:dp[i][j]=qreturn dp[1][n]
这篇关于LintCode 吹气球的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
