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.
- 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
Given [4, 1, 5, 10]
Return 270
nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20
nums = [4, 5, 10] burst 5, get coins 4 * 5 * 10 = 200
nums = [4, 10] burst 4, get coins 1 * 4 * 10 = 40
nums = [10] burst 10, get coins 1 * 10 * 1 = 10
Total coins 20 + 200 + 40 + 10 = 270
Dynamic Programming Solution
A straightforward solution is to use recursion. Take the given example[4, 1, 5, 10].
The following recursion tree shows that the recursive approach has an overlapping subproblems issue.
4, 1, 5, 10
1, 5, 10 4, 5, 10 4, 1, 10, 4, 1, 5
5, 10 1, 10 1, 5 5, 10 4, 10 4,5 1, 10 4,10 4,1 1,5 4,5 4,1
Dynamic Programming Solution
State: T[i][j] stores the max value of bursting ballons i to j and the last ballon that is bursted to get this max.
Function: T[i][j].maxV = max{T[i][k - 1].maxV + T[k + 1][j].maxV + arr[i - 1] * arr[k] * arr[j + 1]};
T[i][j].lastBurstIdx is the k in [i, j] that gives the max value to T[i][j].maxV.
Init: T[i][i].maxV = arr[i - 1] * arr[i] * arr[i + 1]; T[i][j].lastBurstIdx = i.
1 import java.util.Stack; 2 3 class Entry { 4 int maxV; 5 int lastBurstIdx; 6 Entry(int v, int i) { 7 this.maxV = v; 8 this.lastBurstIdx = i; 9 } 10 } 11 public class BurstBallon { 12 private Stack<Integer> burstSeq; 13 public int getMaxPoint(int[] arr) { 14 burstSeq = new Stack<Integer>(); 15 if(arr == null || arr.length == 0) { 16 return 0; 17 } 18 Entry[][] T = new Entry[arr.length][arr.length]; 19 for(int i = 0; i < T.length; i++) { 20 for(int j = i; j < T.length; j++) { 21 T[i][j] = new Entry(0, -1); 22 } 23 } 24 for(int i = 0; i < T.length; i++) { 25 int left = i - 1 >= 0 ? arr[i - 1] : 1; 26 int right = i + 1 < T.length ? arr[i + 1] : 1; 27 T[i][i].maxV = left * arr[i] * right; 28 T[i][i].lastBurstIdx = i; 29 } 30 for(int len = 2; len <= arr.length; len++) { 31 for(int i = 0; i <= arr.length - len; i++) { 32 int j = i + len - 1; 33 for(int lastBurst = i; lastBurst <= j; lastBurst++) { 34 int outerLeft = (i - 1) >= 0 ? arr[i - 1] : 1; 35 int outerRight = (j + 1) < arr.length ? arr[j + 1] : 1; 36 int midValue = outerLeft * arr[lastBurst] * outerRight; 37 int leftMax = i <= lastBurst - 1 ? T[i][lastBurst - 1].maxV : 0; 38 int rightMax = lastBurst + 1 <= j ? T[lastBurst + 1][j].maxV : 0; 39 int currValue = leftMax + midValue + rightMax; 40 if(currValue > T[i][j].maxV) { 41 T[i][j].maxV = currValue; 42 T[i][j].lastBurstIdx = lastBurst; 43 } 44 } 45 } 46 } 47 //reconstruct one burst sequence that gives the best result 48 reconstructOneBestSequence(T, 0, arr.length - 1, burstSeq); 49 return T[0][arr.length - 1].maxV; 50 } 51 private void reconstructOneBestSequence(Entry[][] T, int start, int end, Stack<Integer> burstSeq) { 52 if(end < start) { 53 return; 54 } 55 burstSeq.push(T[start][end].lastBurstIdx); 56 reconstructOneBestSequence(T, start, T[start][end].lastBurstIdx - 1, burstSeq); 57 reconstructOneBestSequence(T, T[start][end].lastBurstIdx + 1, end, burstSeq); 58 } 59 public static void main(String[] args) { 60 int[] arr = {4,1,5,10}; 61 BurstBallon test = new BurstBallon(); 62 //expect 270 63 System.out.println(test.getMaxPoint(arr)); 64 //expect 1, 2, 0, 3 65 while(!test.burstSeq.isEmpty()) { 66 System.out.println(test.burstSeq.pop()); 67 } 68 } 69 }
[Coding Made Simple] Burst Balloon
原文：http://www.cnblogs.com/lz87/p/7288854.html