|
26 | 26 | */
|
27 | 27 |
|
28 | 28 | 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 rth 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 rth 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); |
52 | 41 | }
|
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++; |
58 | 53 | }
|
| 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]; |
59 | 62 | }
|
60 |
| - return dp[l][r][k]; |
61 | 63 | }
|
62 | 64 | }
|
0 commit comments