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:
- 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
这个题目的思路也是利用 区间Dynamic Programming, 思想跟类似,
动态表达式为:
dp[i][j] 是得到的 [i,j] 里面气球的最大值
for k in [i,j]:
value_m = ballons[i-1] * ballons[k] * ballons[j+1]
dp[i][j] = max(dp[i][j], dp[i][k-1] + value_m + dp[k+1][j])
init:
dp[i][i] = ballons[i-1]* ballons[i]* ballons[i+1]
dp[i][j] = 0 if j < i
1. Constraints
1) size [0, 500]
2) element [0, 100]
2. Ideas
Dynamic Programming T: O(n^2) S; O(n^2)
3. Code
class Solution: def burstBallons(self, nums): n = len(nums) ballons = [1] + nums + [1] # plus the corner case dp = [[0]*(n+2) for _ in range(n+2)] # for corner case flag = [[0]*(n+2) for _ in range(n+2)] def helper(l, r): if flag[l][r]: return dp[l][r] if l == r: dp[l][r] = ballons[l-1] * ballons[l] * ballons[l+1] elif l < r: for k in range(l, r+1): # k belongs [l, r], so it is r + 1 value_m = ballons[l-1] * ballons[k] * ballons[r+1] value_l = helper(l, k-1) value_r = helper(k+1, r) dp[l][r] = max(dp[l][r], value_l + value_m + value_r) flag[l][r] = 1 return dp[l][r] return helper(1, n)