forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode01_BurstBalloons.java
More file actions
107 lines (100 loc) · 3.12 KB
/
Code01_BurstBalloons.java
File metadata and controls
107 lines (100 loc) · 3.12 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
package class46;
// 本题测试链接 : https://leetcode.com/problems/burst-balloons/
public class Code01_BurstBalloons {
public static int maxCoins0(int[] arr) {
// [3,2,1,3]
// [1,3,2,1,3,1]
int N = arr.length;
int[] help = new int[N + 2];
for (int i = 0; i < N; i++) {
help[i + 1] = arr[i];
}
help[0] = 1;
help[N + 1] = 1;
return func(help, 1, N);
}
// L-1位置，和R+1位置，永远不越界，并且，[L-1] 和 [R+1] 一定没爆呢！
// 返回，arr[L...R]打爆所有气球，最大得分是什么
public static int func(int[] arr, int L, int R) {
if (L == R) {
return arr[L - 1] * arr[L] * arr[R + 1];
}
// 尝试每一种情况，最后打爆的气球，是什么位置
// L...R
// L位置的气球，最后打爆
int max = func(arr, L + 1, R) + arr[L - 1] * arr[L] * arr[R + 1];
// R位置的气球，最后打爆
max = Math.max(max, func(arr, L, R - 1) + arr[L - 1] * arr[R] * arr[R + 1]);
// 尝试所有L...R，中间的位置，(L,R)
for (int i = L + 1; i < R; i++) {
// i位置的气球，最后打爆
int left = func(arr, L, i - 1);
int right = func(arr, i + 1, R);
int last = arr[L - 1] * arr[i] * arr[R + 1];
int cur = left + right + last;
max = Math.max(max, cur);
}
return max;
}
public static int maxCoins1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int N = arr.length;
int[] help = new int[N + 2];
help[0] = 1;
help[N + 1] = 1;
for (int i = 0; i < N; i++) {
help[i + 1] = arr[i];
}
return process(help, 1, N);
}
// 打爆arr[L..R]范围上的所有气球，返回最大的分数
// 假设arr[L-1]和arr[R+1]一定没有被打爆
public static int process(int[] arr, int L, int R) {
if (L == R) {// 如果arr[L..R]范围上只有一个气球，直接打爆即可
return arr[L - 1] * arr[L] * arr[R + 1];
}
// 最后打爆arr[L]的方案，和最后打爆arr[R]的方案，先比较一下
int max = Math.max(arr[L - 1] * arr[L] * arr[R + 1] + process(arr, L + 1, R),
arr[L - 1] * arr[R] * arr[R + 1] + process(arr, L, R - 1));
// 尝试中间位置的气球最后被打爆的每一种方案
for (int i = L + 1; i < R; i++) {
max = Math.max(max, arr[L - 1] * arr[i] * arr[R + 1] + process(arr, L, i - 1) + process(arr, i + 1, R));
}
return max;
}
public static int maxCoins2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int N = arr.length;
int[] help = new int[N + 2];
help[0] = 1;
help[N + 1] = 1;
for (int i = 0; i < N; i++) {
help[i + 1] = arr[i];
}
int[][] dp = new int[N + 2][N + 2];
for (int i = 1; i <= N; i++) {
dp[i][i] = help[i - 1] * help[i] * help[i + 1];
}
for (int L = N; L >= 1; L--) {
for (int R = L + 1; R <= N; R++) {
int ans = help[L - 1] * help[L] * help[R + 1] + dp[L + 1][R];
ans = Math.max(ans, help[L - 1] * help[R] * help[R + 1] + dp[L][R - 1]);
for (int i = L + 1; i < R; i++) {
ans = Math.max(ans, help[L - 1] * help[i] * help[R + 1] + dp[L][i - 1] + dp[i + 1][R]);
}
dp[L][R] = ans;
}
}
return dp[1][N];
}
}