LeetCode link

first thought

  • The same as Matrix chain multiplication, the maximum value from i to j is equal to the max of it’s sub cases.
  1. choose i ,choose i+1 to j-1, choose j
  2. choose i ,choose i+1 to j
  3. choose i to j-1, choose j

solution

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
class Solution {
    public int removeBoxes(int[] boxes) {
        if (boxes == null || boxes.length < 1) {
            return 0;
        }
        int n = boxes.length;
        if (n == 1) {
            return 1;
        }
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
            if (i < n - 1) {
                dp[i][i + 1] = dp[i] == dp[i + 1] ? 4 : 2;
            }
        }
        for (int k = 1; k < n - 1; k++) {
            for (int i = 0; i < n - k; i++) {
                int j = i + k;
                int s1 = 1 + dp[i + 1][j - 1] + 1;
                int s2 = 1 + dp[i + 1][j];
                int s3 = dp[i][j - 1] + 1;
                if (dp[i] == dp[j]) {
                    s1 = 4 + dp[i + 1][j - 1];
                }
                dp[i][j] = Math.max(s1, Math.max(s2, s3));
            }
        }
        return dp[0][n - 1];
    }
}

problem

WA.

reason

It’s not the same as matrix ,because in the matrix we multiplicate one number each time, but in this problem, different split can influence the combination result as we can choose not only one number each time.

modification

The DFS answer

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
class Solution {
    public int removeBoxes(int[] boxes) {
        if (boxes == null || boxes.length < 1) {
            return 0;
        }
        int n = boxes.length;
        int[][][] scores = new int[n][n][n];
        return this.dfs(boxes, 0, n - 1, 0, scores);
    }
    private int dfs(int[] boxes, int i, int j, int k, int[][][] scores) {
        if (i > j) {
            return 0;
        }
        if (scores[i][j][k] > 0) {
            return scores[i][j][k];
        }
        int result = (1 + k) * (1 + k) + this.dfs(boxes, i + 1, j , 0, scores);
        for (int r = i + 1; r <= j; r++) {
            if (boxes[r] == boxes[i]) {
                result = Math.max(result, this.dfs(boxes, i + 1, r - 1, 0, scores) + this.dfs(boxes, r, j, k + 1, scores));
            }
        }
        scores[i][j][k] = result;
        return result;
    }
}

another solution

  • According to the DFS solution, here’s the DP solution.
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
class Solution {
    public int removeBoxes(int[] boxes) {
        if (boxes == null || boxes.length < 1) {
            return 0;
        }
        int n = boxes.length;
        int[][][] scores = new int[n][n][n];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                scores[i][i][k] = (1 + k) * (1 + k);
            }
        }
        for (int r = 1; r < n; r++) {
            for (int i = 0; i + r < n; i++) {
                int j = i + r;
                for (int k = 0; k <= i; k ++) {
                    int result = (1 + k) * (1 + k) + scores[i + 1][j][0];
                    for (int m = i + 1; m <= j; m++) {
                        if (boxes[m] == boxes[i]) {
                            result = Math.max(result, scores[i + 1][m - 1][0] + scores[m][j][k + 1]);
                        }
                    }
                    scores[i][j][k] = result;
                }
            }
        }
        return scores[0][n - 1][0];
    }
}