Skip to content

546. Remove Boxes 👍

  • Time: $O(n^4)$
  • Space: $O(n^3)$
 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
class Solution {
 public:
  int removeBoxes(vector<int>& boxes) {
    const int n = boxes.size();
    // dp[i][j][k] := max score of boxes[i..j] if k boxes eqaul to boxes[j]
    dp.resize(n, vector<vector<int>>(n, vector<int>(n)));
    return removeBoxes(boxes, 0, n - 1, 0);
  }

 private:
  vector<vector<vector<int>>> dp;

  int removeBoxes(const vector<int>& boxes, int i, int j, int k) {
    if (i > j)
      return 0;
    if (dp[i][j][k] > 0)
      return dp[i][j][k];

    int r = j;
    int sameBoxes = k + 1;
    while (r > 0 && boxes[r - 1] == boxes[r]) {
      --r;
      ++sameBoxes;
    }
    dp[i][j][k] = removeBoxes(boxes, i, r - 1, 0) + sameBoxes * sameBoxes;

    for (int p = i; p < r; ++p)
      if (boxes[p] == boxes[r])
        dp[i][j][k] = max(dp[i][j][k], removeBoxes(boxes, i, p, sameBoxes) +
                                           removeBoxes(boxes, p + 1, r - 1, 0));

    return dp[i][j][k];
  }
};

 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
class Solution {
  public int removeBoxes(int[] boxes) {
    final int n = boxes.length;
    // dp[i][j][k] := max score of boxes[i..j] if k boxes eqaul to boxes[j]
    dp = new int[n][n][n];
    return removeBoxes(boxes, 0, n - 1, 0);
  }

  private int[][][] dp;

  private int removeBoxes(int[] boxes, int i, int j, int k) {
    if (i > j)
      return 0;
    if (dp[i][j][k] > 0)
      return dp[i][j][k];

    int r = j;
    int sameBoxes = k + 1;
    while (r > 0 && boxes[r - 1] == boxes[r]) {
      --r;
      ++sameBoxes;
    }
    dp[i][j][k] = removeBoxes(boxes, i, r - 1, 0) + sameBoxes * sameBoxes;

    for (int p = i; p < r; ++p)
      if (boxes[p] == boxes[r])
        dp[i][j][k] = Math.max(dp[i][j][k], removeBoxes(boxes, i, p, sameBoxes) +
                                                removeBoxes(boxes, p + 1, r - 1, 0));

    return dp[i][j][k];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def removeBoxes(self, boxes: List[int]) -> int:
    # dp(i, j, k) := max score of boxes[i..j] if k boxes equal to boxes[j]
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      if i > j:
        return 0

      r = j
      sameBoxes = k + 1
      while r > 0 and boxes[r - 1] == boxes[r]:
        r -= 1
        sameBoxes += 1
      ans = dp(i, r - 1, 0) + sameBoxes * sameBoxes

      for p in range(i, r):
        if boxes[p] == boxes[r]:
          ans = max(ans, dp(i, p, sameBoxes) + dp(p + 1, r - 1, 0))

      return ans

    return dp(0, len(boxes) - 1, 0)