https://leetcode.com/problems/burst-balloons/
//trick: add head and tail element with 1 for edge usage, final result return dp[1][m]!
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
(2) 0 ≤
(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
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
Answer:
Method: DP + divide & conquer!
Suppose num[k] is the last balloon bursted in interval [i,j], so last step we will get coin:
num[i-1]*num[k]*num[j+1]
//dp formular:
dp(i,j) = Max{dp(i,k-1) + num[i-1]*num[k]*num[j+1] + dp(k+1,j)} , k=[i,j], when i<=j
dp(i,j) = 0, when i>j
dp(i,j) = 0, when i>j
public class Solution {
public int maxCoins(int[] nums) {
int m=nums.length;
if(m==0)return 0;
int[] nums2 = new int[m+2];
int[][] dp = new int[m+2][m+2];
//trick: add head and tail element with 1 for edge usage, final result return dp[1][m]!
nums2[0]=1;
nums2[m+1]=1;
for(int i=1;i<=m;++i){
nums2[i]=nums[i-1];
}
for(int j=1;j<=m;++j){
for(int i=j;i>=1;--i){
//dp common case func
for(int k=i;k<=j;++k){
dp[i][j]=Math.max(dp[i][j], dp[i][k-1]+dp[k+1][j] + nums2[i-1]*nums2[k]*nums2[j+1]);
}
}
}
return dp[1][m];
}
}
No comments:
Post a Comment