forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBurst Balloons.java
More file actions
executable file
·121 lines (94 loc) · 3.54 KB
/
Burst Balloons.java
File metadata and controls
executable file
·121 lines (94 loc) · 3.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
其实会做之后挺好想的一个DP。
dp[i][j] = balloons i~j 之间的sum. 然后找哪个点开始burst? 设为x。
For loop 所有的点作为x， 去burst。
每次burst都切成了三份：左边可以recusive 求左边剩下的部分的最大值 + 中间3项相乘 + 右边递归下去求最大值。
这个是momorization, 而不纯是DP
因为recursive了，其实还是搜索，但是memorize了求过的值，节省了Processing
```
/*
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
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
Credits:
Special thanks to @peisi for adding this problem and creating all test cases.
Hide Company Tags Google
Show Tags
Divide and Conquer Dynamic Programming
*/
/*
Thoughts: as seen in dicussion. Build DP.
State:
dp[i][j]: the number of max coins can collect between i and j.
For a position x in [i,j], where to burst it? So this goes into a divide and conquer method.
Burst at x, track the sum, and record the max into dp[i][j]
Function:
dp[i][j] = Math.max(dp[i][j], DP(i, x-1) + nums[x-1]*nums[x]*nums[x+1] + DP(x+1, j))
Init:
create dp[n+2][n+2]. (from 0 to n+1)
dp[0][1] = 1;
dp[n][n+1] = 1;
Return:
dp[1][n]
DP(int i, int j, int[][] dp)
Need to redo that nums.
*/
public class Solution {
int[][] dp;
int[] values;
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
dp = new int[n + 2][n + 2];
//Initialize new array
values = new int[n + 2];
values[0] = values[n + 1] = 1;
for (int i = 1; i < n + 1; i++) {
values[i] = nums[i - 1];
}
return DP(1, n);
}
public int DP(int i, int j){
if (dp[i][j] > 0) {//momorization
return dp[i][j];
}
for (int x = i; x <= j; x++) {
dp[i][j] = Math.max(dp[i][j], DP(i, x - 1) + values[i-1]*values[x]*values[j+1] + DP(x + 1, j));
}
return dp[i][j];
}
}
/*
用了recursive + memorization, 但是也可以用传统的DP，比如：
for (int length = 1; length < n; length++) [
for (int = 0; i < n-1; i++) {
j = i + length;
if length == 1:
dp[i][j] = A[i] * A[j] + A[i]
else:
dp[i][j] = max {}
}
}
*/
/*
My Thought: TOO COMPLEX. Should go with the easy DP approach. Also, using a hashMap to trach all the patterns,
this might not be applicable: because as the integer array's length goes up, there will be too many possible
combinations to store in hashamp.
Burst each balloon, and DFS into each branch, calcualte the sum + each balloon-burst's product.
Also, use a HahsMap<"Value combination", max value>. to reduce the # of re-calculation.
convert nums into string, and in DFS, we don't even need bakc-tracking
helper(list, sum)
Thoughts:http://www.cnblogs.com/grandyang/p/5006441.html
dp[i,j]: burst range [i~j]'s max coins.
*/
```