# Where is wrong(C++)？

• ``````class Solution {
public:
int removeBoxes(vector<int>& boxes) {
if (boxes.empty()) return 0;
boxes.push_back(-1);
// preprocessing
// [1,1,1,3,3,2,3,3,3,1,1] would become
// color : [1,3,2,3,1]
// length :   [3,2,1,3,2]
vector<int> color;
vector<int> length;
int currColor, currLen;
for (int i = 0; i < boxes.size(); i++) {
if (i == 0 || boxes[i] != boxes[i - 1]) {
if (i > 0 && boxes[i] != boxes[i - 1]) {
color.push_back(currColor);
length.push_back(currLen);
}
currColor = boxes[i];
currLen = 1;
} else {
currLen++;
}
}
vector<vector<int>> dp(color.size(), vector<int>(color.size()));
for (int offset = 0; offset < color.size(); offset++) {
for (int i = 0; i < color.size() - offset; i++) {
if (offset == 0) dp[i][i + offset] = length[i] * length[i];
else if (offset == 1) dp[i][i + offset] = dp[i][i] + dp[i + offset][i + offset];
else {
if (color[i] == color[i + offset]) {
// merge color i
dp[i][i + offset] = 0;
int count = length[i], prev = i;
for (int t = i + 1; t <= i + offset; t++) {
if (color[t] == color[i]) {
count += length[t];
dp[i][i + offset] += dp[prev + 1][t - 1];
prev = t;
}
}
dp[i][i + offset] += count * count;
} else {
dp[i][i + offset] = INT_MIN;
}
// dp[i][j] = max(dp[i][j], dp[i][t] + dp[t + 1][j]) where t from i to j - 1
for (int t = i; t < i + offset; t++) {
dp[i][i + offset] = max(dp[i][i + offset], dp[i][t] + dp[t + 1][i + offset]);
}
}
}
}
return dp[0].back();
}
};
``````

• I know where I am wrong.

``````class Solution {
public:
int removeBoxes(vector<int>& boxes) {
if (boxes.empty()) return 0;
boxes.push_back(-1);
// preprocessing
// [1,1,1,3,3,2,3,3,3,1,1] would become
// color : [1,3,2,3,1]
// length :   [3,2,1,3,2]
vector<int> color;
vector<int> length;
int currColor, currLen;
for (int i = 0; i < boxes.size(); i++) {
if (i == 0 || boxes[i] != boxes[i - 1]) {
if (i > 0 && boxes[i] != boxes[i - 1]) {
color.push_back(currColor);
length.push_back(currLen);
}
currColor = boxes[i];
currLen = 1;
} else {
currLen++;
}
}
vector<vector<int>> dp(color.size(), vector<int>(color.size()));
for (int offset = 0; offset < color.size(); offset++) {
for (int i = 0; i < color.size() - offset; i++) {
if (offset == 0) dp[i][i + offset] = length[i] * length[i];
else if (offset == 1) dp[i][i + offset] = dp[i][i] + dp[i + offset][i + offset];
else {
dp[i][i + offset] = INT_MIN;
if (color[i] == color[i + offset]) {
// !!! middle boxes with the same color maybe not participate in merging
dfs(dp, color, length, i + offset, i, i + 1, length[i] + length[i + offset], 0, dp[i][i + offset]);
}
// dp[i][j] = max(dp[i][j], dp[i][t] + dp[t + 1][j]) where t from i to j - 1
for (int t = i; t < i + offset; t++) {
dp[i][i + offset] = max(dp[i][i + offset], dp[i][t] + dp[t + 1][i + offset]);
}
}
}
}
return dp[0].back();
}
void dfs(vector<vector<int>>& dp, vector<int>& color, vector<int>& length, int end, int prev, int curr, int count, int sum, int& res) {
if (curr == end) {
res = max(res, sum + dp[prev + 1][end - 1] + count * count);
} else {
if (color[curr] == color[end]) {
dfs(dp, color, length, end, curr, curr + 1, count + length[curr], sum + dp[prev + 1][curr - 1], res);
}
dfs(dp, color, length, end, prev, curr + 1, count, sum, res);
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.