leetcode Burst Balloons - 细语呢喃
leetcode Burst Balloons
Given
n
balloons, indexed from0
ton-1
. Each balloon is painted with a number on it represented by arraynums
. You are asked to burst all the balloons. If the you burst ballooni
you will getnums[left] * nums[i] * nums[right]
coins. Hereleft
andright
are adjacent indices ofi
. After the burst, theleft
andright
then becomes adjacent.Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imaginenums[-1] = nums[n] = 1
. They are not real therefore you can not burst them.
(2) 0 ≤n
≤ 500, 0 ≤nums[i]
≤ 100Example:
Given
[3, 1, 5, 8]
Return
167
题意:
给定n个气球。每次你可以打破一个,打破第i个,那么你会获得nums[left] * nums[i] * nums[right]个积分。 (nums[-1] = nums[n] = 1)求你可以获得的最大积分数
思路:
一开始想dp[i][j] 为第 i 天打破第j 个气球,然后枚举上一轮打破的为第k个气球 dp[i][j] =max( dp[i �C 1][k] + left * nums[j] * right) (当然要记录都打了哪些O) 复杂度 O(n^3) 然而TLE (python)
看了discuss是dp[i][j]为打破的气球为i~j之间。
我们可以想象:最后的剩下一个气球为i的时候,可以获得的分数为:nums[-1]*nums[i]*nums[n].
那么介于i,j之间的x,有: dp[i][j] = max(dp[i][j], dp[i][x �C 1] + nums[i �C 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
C++跑1330MS ,JAVA 187MS ,python TLE 。。。。python TLE 可以理解,但C++比JAVA这题还慢这不合理。。。。可能是vector太慢?
Read full article from leetcode Burst Balloons - 细语呢喃
No comments:
Post a Comment