Remove boxes

Array Dynamic Programming Memoization

49.3% acceptance

Feb 19, 2026

2461

136

You are given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= 1), remove them and get k * k points. Return the maximum points you can get.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn remove_boxes(boxes: Vec<i32>) -> i32 {
    let n = boxes.len();
    let mut memo = vec![vec![vec![-1i32; n]; n]; n];
    fn dp(boxes: &[i32], memo: &mut Vec<Vec<Vec<i32>>>, i: usize, j: usize, k: usize) -> i32 {
      if i > j { return 0; }
      if memo[i][j][k] >= 0 { return memo[i][j][k]; }
      let mut res = (k as i32 + 1) * (k as i32 + 1)
        + if i < j { dp(boxes, memo, i + 1, j, 0) } else { 0 };
      for m in (i + 1)..=j {
        if boxes[m] == boxes[i] {
          let mid = if i + 1 < m { dp(boxes, memo, i + 1, m - 1, 0) } else { 0 };
          let right = dp(boxes, memo, m, j, k + 1);
          res = res.max(mid + right);
        }
      }
      memo[i][j][k] = res;
      res
    }
    dp(&boxes, &mut memo, 0, n - 1, 0)
  }
}