8000 refactor 546 · kevinadol/Leetcode@b7c3160 · GitHub
[go: up one dir, main page]

Skip to content

Commit b7c3160

Browse files
refactor 546
1 parent 7fb9c68 commit b7c3160

File tree

1 file changed

+31
-29
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+31
-29
lines changed

src/main/java/com/fishercoder/solutions/_546.java

Lines changed: 31 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -26,37 +26,39 @@
2626
*/
2727

2828
public class _546 {
29-
/**
30-
* credit: https://leetcode.com/articles/remove-boxes/#approach-2-using-dp-with-memorizationaccepted
31-
*
32-
* For an entry in dp[l][r][k], l represents the starting index of the subarray,
33-
* r represents the ending index of the subarray
34-
* and k represents the number of elements similar to the r​th element
35-
* following it which can be combined to obtain the point information to be stored in dp[l][r][k].
36-
*/
37-
public int removeBoxes(int[] boxes) {
38-
int[][][] dp = new int[100][100][100];
39-
return calculatePoints(boxes, dp, 0, boxes.length - 1, 0);
40-
}
41-
42-
public int calculatePoints(int[] boxes, int[][][] dp, int l, int r, int k) {
43-
if (l > r) {
44-
return 0;
45-
}
46-
if (dp[l][r][k] != 0) {
47-
return dp[l][r][k];
48-
}
49-
while (r > l && boxes[r] == boxes[r - 1]) {
50-
r--;
51-
k++;
29+
public static class Solution1 {
30+
/**
31+
* credit: https://leetcode.com/articles/remove-boxes/#approach-2-using-dp-with-memorizationaccepted
32+
*
33+
* For an entry in dp[l][r][k], l represents the starting index of the subarray,
34+
* r represents the ending index of the subarray
35+
* and k represents the number of elements similar to the r​th element
36+
* following it which can be combined to obtain the point information to be stored in dp[l][r][k].
37+
*/
38+
public int removeBoxes(int[] boxes) {
39+
int[][][] dp = new int[100][100][100];
40+
return calculatePoints(boxes, dp, 0, boxes.length - 1, 0);
5241
}
53-
dp[l][r][k] = calculatePoints(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
54-
for (int i = l; i < r; i++) {
55-
if (boxes[i] == boxes[r]) {
56-
dp[l][r][k] = Math.max(dp[l][r][k],
57-
calculatePoints(boxes, dp, l, i, k + 1) + calculatePoints(boxes, dp, i + 1, r - 1, 0));
42+
43+
public int calculatePoints(int[] boxes, int[][][] dp, int l, int r, int k) {
44+
if (l > r) {
45+
return 0;
46+
}
47+
if (dp[l][r][k] != 0) {
48+
return dp[l][r][k];
49+
}
50+
while (r > l && boxes[r] == boxes[r - 1]) {
51+
r--;
52+
k++;
5853
}
54+
dp[l][r][k] = calculatePoints(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
55+
for (int i = l; i < r; i++) {
56+
if (boxes[i] == boxes[r]) {
57+
dp[l][r][k] = Math.max(dp[l][r][k],
58+
calculatePoints(boxes, dp, l, i, k + 1) + calculatePoints(boxes, dp, i + 1, r - 1, 0));
59+
}
60+
}
61+
return dp[l][r][k];
5962
}
60-
return dp[l][r][k];
6163
}
6264
}

0 commit comments

Comments
 (0)
0