GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #546 - Remove Boxes - LeetCode JavaScript Solutions

Back to all solutions

#546 - Remove Boxes

Hard • View on LeetCode • View on GitHub

Array Dynamic Programming Memoization

Problem Description

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

/**
 * @param {number[]} boxes
 * @return {number}
 */
var removeBoxes = function(boxes) {
  const dp = new Array(boxes.length).fill().map(() => {
    return new Array(boxes.length).fill().map(() => new Array(boxes.length + 1).fill(0));
  });
  return dfs(0, boxes.length - 1, 0);

  function dfs(l, r, k) {
    if (l > r) return 0;
    if (dp[l][r][k]) return dp[l][r][k];
    let i = l;
    let count = k + 1;
    while (i < r && boxes[i] === boxes[i + 1]) {
      i++;
      count++;
    }
    let max = count * count + dfs(i + 1, r, 0);
    for (let m = i + 1; m <= r; m++) {
      if (boxes[l] === boxes[m]) {
        max = Math.max(max, dfs(i + 1, m - 1, 0) + dfs(m, r, count));
      }
    }
    return dp[l][r][k] = max;
  }
};

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.