[Link] https://leetcode.com/problems/burst-balloons/
Bottom-Up(Fast)
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
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] ball = new int[n + 2];
int[][] dp = new int[n][n];
for(int i = 1; i <= n; i++) ball[i] = nums[i - 1];
ball[0] = ball[n + 1] = 1;
for(int i = 1; i <= n; i++) dp[i - 1][i - 1] = ball[i - 1] * ball[i] * ball[i + 1];
for(int dl = 1; dl < n; dl++) { // len is dl + 1
for(int l = 1, ul = n - dl; l <= ul; l++) {
int max = -1, mul = ball[l - 1] * ball[l + dl + 1];
max = Math.max(max, ball[l] * mul + dp[l][l + dl - 1]);
max = Math.max(max, ball[l + dl] * mul + dp[l - 1][l + dl - 2]);
for(int k = l + 1; k < l + dl; k++)
max = Math.max(max, dp[l - 1][k - 2] + dp[k][l + dl - 1] + ball[k] * mul);
dp[l - 1][l + dl - 1] = max;
}
}
return dp[0][n-1];
}
}
Top-Down(Slow)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] ball = new int[n + 2];
int[][] dp = new int[n][n];
ball[0] = 1;
for(int i = 1; i <= n; i++) ball[i] = nums[i - 1];
ball[n + 1] = 1;
return dfs(dp, ball, 1, n);
}
int dfs(int[][] dp, int[] ball, int left, int right) {
if(left > right) return 0;
if(dp[left - 1][right - 1] != 0) return dp[left - 1][right - 1];
if(left == right) return dp[left - 1][left - 1] = ball[left - 1] * ball[left] * ball[left + 1];
for(int i = left; i <= right; i++) {
dp[left - 1][right - 1] = Math.max(dp[left - 1][right - 1], ball[left - 1] * ball[i] * ball[right + 1] + dfs(dp, ball, left, i - 1) + dfs(dp, ball, i + 1, right));
}
return dp[left - 1][right - 1];
}
}
Wrong code( O(n^2) )
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
class Solution {
public int maxCoins(int[] nums) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
for(int e: nums) list.add(e);
list.add(1);
int sum = 0, max, maxIdx;
while(list.size() > 2) {
max = Integer.MIN_VALUE;
maxIdx = -1;
// println(list);
for(int i = 1; i < list.size() - 1; i++) {
int dcoin = getDiff(list, i);
// print(" [ " + i + " : " + dcoin + " ] &&");
if(dcoin > max) {
maxIdx = i;
max = dcoin;
}
}
sum += getCoin(list, maxIdx);
// println("\nidx: " + maxIdx + " , ballon: " + list.get(maxIdx) + " , sum: " + sum);
list.remove(maxIdx);
}
return sum;
}
int getCoin(ArrayList<Integer> list, int i) {
return getOrDefault(list, i - 1) * getOrDefault(list, i) * getOrDefault(list, i + 1);
}
int getDiff(ArrayList<Integer> list, int i) {
return getOrDefault(list, i - 2) * getOrDefault(list, i - 1) * (getOrDefault(list, i + 1) - getOrDefault(list, i))
+ getOrDefault(list, i + 1) * getOrDefault(list, i + 2) * (getOrDefault(list, i - 1) - getOrDefault(list, i));
}
int getOrDefault(ArrayList<Integer> list, int idx) {
if(idx < 0 || idx >= list.size()) return 0;
return list.get(idx);
}
<T> void print(T s) { System.out.print(s); }
<T> void println(T s) { System.out.println(s); }
}