|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 546. Remove Boxes |
5 |
| - * |
6 |
| - * Given several boxes with different colors represented by different positive numbers. |
7 |
| - * You may experience several rounds to remove boxes until there is no box left. |
8 |
| - * Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points. |
9 |
| - * Find the maximum points you can get. |
10 |
| -
|
11 |
| - Example 1: |
12 |
| - Input: |
13 |
| -
|
14 |
| - [1, 3, 2, 2, 2, 3, 4, 3, 1] |
15 |
| - Output: |
16 |
| - 23 |
17 |
| -
|
18 |
| - Explanation: |
19 |
| - [1, 3, 2, 2, 2, 3, 4, 3, 1] |
20 |
| - ----> [1, 3, 3, 4, 3, 1] (3*3=9 points) |
21 |
| - ----> [1, 3, 3, 3, 1] (1*1=1 points) |
22 |
| - ----> [1, 1] (3*3=9 points) |
23 |
| - ----> [] (2*2=4 points) |
24 |
| - Note: The number of boxes n would not exceed 100. |
25 |
| -
|
26 |
| - */ |
27 |
| - |
28 | 3 | public class _546 {
|
29 | 4 | public static class Solution1 {
|
30 | 5 | /**
|
31 | 6 | * credit: https://leetcode.com/articles/remove-boxes/#approach-2-using-dp-with-memorizationaccepted
|
32 |
| - * |
| 7 | + * <p> |
33 | 8 | * For an entry in dp[l][r][k], l represents the starting index of the subarray,
|
34 | 9 | * r represents the ending index of the subarray
|
35 | 10 | * and k represents the number of elements similar to the rth element
|
|
0 commit comments