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.
1def removeBoxes(boxes):
2 memo = {}
3 def dp(l, r, k):
4 if l > r: return 0
5 if (l, r, k) in memo:
6 return memo[(l, r, k)]
7 while r > l and boxes[r] == boxes[r - 1]:
8 r -= 1
9 k += 1
10 memo[(l, r, k)] = dp(l, r - 1, 0) + (k + 1) ** 2
11 for i in range(l, r):
12 if boxes[i] == boxes[r]:
13 memo[(l, r, k)] = max(memo[(l, r, k)], dp(l, i, k + 1) + dp(i + 1, r - 1, 0))
14 return memo[(l, r, k)]
15 return dp(0, len(boxes) - 1, 0)The recursive dp function tries to match different segments of the array and calculates scores accordingly. dp(l, r, k) computes the maximum score for a subarray while considering preprocessing contiguous blocks at index r. By reducing r to a point where we have a different color or run out of elements to compare, we explore subproblems and store results in the memoization table to save on future calculations.
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.