leetcode 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 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
1 2 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
题目地址: leetcode Burst Balloons
题意:
给定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 - 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 - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
这里,为了方便代码书写,我在首尾插入了两个1,所以答案是dp[1][n]
(n为原来的长度)
可以用记忆化搜索也可以直接迭代DP,当然,记忆化搜索更好理解一点。
Divide and Conquer 记忆化搜索
Java 18ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public int DP (int i, int j, int [] nums, int [][] dp) { if (dp[i][j] > 0 ) return dp[i][j]; for (int x = i; x <= j; x++) { dp[i][j] = Math.max(dp[i][j], DP(i, x - 1 , nums, dp) + nums[i - 1 ] * nums[x] * nums[j + 1 ] + DP(x + 1 , j, nums, dp)); } return dp[i][j]; } public int maxCoins (int [] iNums) { int n = iNums.length; int [] nums = new int [n + 2 ]; for (int i = 0 ; i < n; i++) nums[i + 1 ] = iNums[i]; nums[0 ] = nums[n + 1 ] = 1 ; int [][] dp = new int [n + 2 ][n + 2 ]; return DP(1 , n, nums, dp); } }
C++ 76ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int DP (int i, int j, const vector<int > &nums, vector<vector<int > > &dp) { if (dp[i][j] > 0 ) return dp[i][j]; for (int x = i; x <= j; x++) { int temp = DP (i, x - 1 , nums, dp) + nums[i - 1 ] * nums[x] * nums[j + 1 ] + DP (x + 1 , j, nums, dp); if (temp > dp[i][j]) dp[i][j] = temp; } return dp[i][j]; } int maxCoins (vector<int >& nums) { int n = nums.size (); nums.insert (nums.begin (), 1 ); nums.insert (nums.end (), 1 ); vector<vector<int > > dp (n + 2 , vector <int >(n + 2 , 0 )); return DP (1 , n, nums, dp); } };
Python 1100ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution (object ): def maxCoins (self, nums ): """ :type nums: List[int] :rtype: int """ n = len (nums) nums = [1 ] + nums + [1 ] dp = [[0 for j in xrange(n + 2 )] for i in xrange(n + 2 )] def DP (i, j ): if dp[i][j] > 0 : return dp[i][j] for x in xrange(i, j + 1 ): dp[i][j] = max (dp[i][j],DP(i, x - 1 ) + nums[i - 1 ] * nums[x] * nums[j + 1 ]+ DP(x + 1 , j)) return dp[i][j] return DP(1 ,n)
DP
C++跑1330MS ,JAVA 187MS ,python TLE 。。。。python TLE 可以理解,但C++比JAVA这题还慢这不合理。。。。可能是vector太慢?
update at 2015.12.22 :重新提交发现跑快了,目测为了照顾python 把数据量降下来了
Java 15ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public int maxCoins (int [] iNums) { int n = iNums.length; int [] nums = new int [n + 2 ]; for (int i = 0 ; i < n; i++) nums[i + 1 ] = iNums[i]; nums[0 ] = nums[n + 1 ] = 1 ; int [][] dp = new int [n + 2 ][n + 2 ]; for (int k = 1 ; k <= n; k++) { for (int i = 1 ; i <= n - k + 1 ; i++) { int j = i + k - 1 ; for (int x = i; x <= j; x++) { dp[i][j] = Math.max(dp[i][j], dp[i][x - 1 ] + nums[i - 1 ] * nums[x] * nums[j + 1 ] + dp[x + 1 ][j]); } } } return dp[1 ][n]; } }
C++ 36ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0)); for (int k = 1; k <= n; k++) { for (int i = 1; i <= n - k + 1; i++) { int j = i + k - 1; for (int x = i; x <= j; x++) { int temp = dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]; if (dp[i][j] < temp) dp[i][j] = temp; } } } return dp[1][n]; } };