Sponsored
Sponsored
This approach uses recursion and memoization to compute the maximum score recursively. We artificially modify the problem to keep count of contiguous boxes and use a 3D array for memoization. The base case is when there are no boxes left. Recurrence relations deal with choosing to remove a contiguous segment immediately or merge it with other parts of the array by considering different partition points.
Time Complexity: O(n^4). The recursive solution has three dimensions for recursion state, each from 0 to n.
Space Complexity: O(n^3). Needed for memoization storage.
1function removeBoxes(boxes) {
2 const memo = Array.from({ length: 100 }, () => Array.from({ length: 100 }, () => Array(100).fill(0)));
3 function dp(l, r, k) {
4 if (l > r) return 0;
5 if (memo[l][r][k] > 0) return memo[l][r][k];
6 while (r > l && boxes[r] === boxes[r - 1]) {
7 r--;
8 k++;
9 }
10 memo[l][r][k] = dp(l, r - 1, 0) + (k + 1) * (k + 1);
11 for (let i = l; i < r; i++) {
12 if (boxes[i] === boxes[r]) {
13 memo[l][r][k] = Math.max(memo[l][r][k], dp(l, i, k + 1) + dp(i + 1, r - 1, 0));
14 }
15 }
16 return memo[l][r][k];
17 }
18 return dp(0, boxes.length - 1, 0);
19}The JavaScript solution adopts a similar approach, using a 3D array to cache previously computed subproblems. It loops over possible partition points in the array and calculates scores recursively, ensuring that computation is reduced by memoizing results.
This approach converts the recursive problem into an iterative dynamic programming solution. We maintain a 3D table to determine maximum obtainable points for different contiguous subarrays and contingent blocks for each color. We fill the table starting from smaller segments and incrementally consider larger segments while determining scores.
Time Complexity: O(n^4). Similar state iterations but performed iteratively.
Space Complexity: O(n^3). Space used for the iterative 3D table.
1#include <vector>
2using namespace std;
3
4int removeBoxes(vector<int>& boxes) {
5 int n = boxes.size();
6 vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, 0)));
7 for (int len = 1; len <= n; len++) {
for (int l = 0; l <= n - len; l++) {
int r = l + len - 1;
for (int k = 0; k <= l; ++k) {
int res = (k + 1) * (k + 1) + (l < r ? dp[l + 1][r][0] : 0);
for (int m = l + 1; m <= r; ++m) {
if (boxes[m] == boxes[l]) {
res = max(res, dp[l + 1][m - 1][0] + dp[m][r][k + 1]);
}
}
dp[l][r][k] = res;
}
}
}
return dp[0][n - 1][0];
}The solution populates a 3D dp table by fixing lengths and starting index l of segments before solving larger segments. For each possible partition index m where blocks match color l of the segments, scores are merged and computed effectively. The iterative solution ensures no recursion overhead and efficiently computes all subproblem solutions iteratively.