# c++ DFS Solution with Explanation.

• First thank to @waterbucket Memoization DFS C++ ,this answer is inpired by the blogger, but a little different. And the test case is weird,so, I also need help for why the test case is so weird.

Here is the idea.
take an example [1,1,1,3,3,2,4,4,4,5,5].
we then can have another form as below:
(1,3),(3,2),(2,1),(4,3),(5,2). the form (1,3) can be explained as 1,1,1
and the form (3,2) can be explained as 3,3
we can use array number[] and array len[] to reprensent it;
number[1...5] = {1,3,2,4,5}
len[1...5] = {3,2,1,3,2}

here is the key:
we use dp[l][r][k] inform the maximum points got from (number[l],len[l]),(number[l+1],len[l+1])...(number[r-1],len[r-1]),(number[r],len[r]+k).

for (number[r],len[r]+k) segment. we either combine it with the former one or we can just remove it.

1.remove it: we can get the result:R1=dp[l][r-1][0] + (len[r] + k)*(len[r]+k);
2.combine it with the former p, the result is:R2 = dp[l][p][len[r]+k] + dp[p+1][r-1][0]
so the answer is max(R1,R2).

here is the code

``````
#define MAXN 101

class Solution {
int number[MAXN], len[MAXN];
public:
int removeBoxes(vector<int> &boxes) {
memset(number,0, sizeof(number));
memset(len,0, sizeof(len));
int n = int(boxes.size());
int dp[100][100][100] = {0};
int colcnt = 0, calc = 1;
for (int i = 0; i < boxes.size(); i++) {
if (boxes[i] == boxes[i + 1])
calc += 1;
else {
number[colcnt] = boxes[i];
len[colcnt] = calc;
calc = 1;
colcnt += 1;
}
}
return dfs(boxes, dp, 0, colcnt-1, 0);
}
int dfs(vector<int>& boxes,int dp[100][100][100], int l,int r,int k){
if (l>r) return 0;
if (dp[l][r][k]!=0) return dp[l][r][k];
if (l == r) return (len[r]+k)*(len[r]+k);
dp[l][r][k] = dfs(boxes,dp,l,r-1,0) + (len[r]+k)*(len[r]+k);
for (int i=l; i<r; i++){
if (number[i]==number[r]){
dp[l][r][k] = max(dp[l][r][k], dfs(boxes,dp,l,i,len[r]+k) + dfs(boxes,dp,i+1,r-1,0));
}
}
return dp[l][r][k];
}
};

``````

but the code here will meet two case error.
one is {13,17,6,14,9,18,11,14,8,10,11,12,19,16,15,7,3,11,19,9};
the other is {14,13,3,14,13,17,9,4,5,20,2,15,12,1,4,15,2,16,11,8};
both case can pass if you run it seprately, but submit solution, the answer is wrong.I cannot find why.

• Hi, @supersj , I try a similar idea with yours. You could see my post Java Preprocessing DFS + Memoization, less space needed here.

• #define MAXN 101

class Solution {
int number[MAXN], len[MAXN];
public:
int removeBoxes(vector<int> &boxes) {
memset(number,0, sizeof(number));
memset(len,0, sizeof(len));
int n = int(boxes.size());
int dp[100][100][100] = {0};
int colcnt = 0, calc = 1;
for (int i = 0; i < boxes.size(); i++) {
if (boxes[i] == boxes[i + 1])
calc += 1;
else {
number[colcnt] = boxes[i];
len[colcnt] = calc;
calc = 1;
colcnt += 1;
}
}
return dfs(boxes, dp, 0, colcnt-1, 0);
}
int dfs(vector<int>& boxes,int dp[100][100][100], int l,int r,int k){
if (l>r) return 0;
if (dp[l][r][k]!=0) return dp[l][r][k];
if (l == r) return (len[r]+k)(len[r]+k);
dp[l][r][k] = dfs(boxes,dp,l,r-1,0) + (len[r]+k)
(len[r]+k);
for (int i=l; i<r; i++){
if (number[i]==number[r]){
dp[l][r][k] = max(dp[l][r][k], dfs(boxes,dp,l,i,len[r]+k) + dfs(boxes,dp,i+1,r-1,0));
}
}
return dp[l][r][k];
}
};

however, when I try to copy your code to submit so that I can compare it with mine, leetcode gives an unsuccessful test case:
Input:
[13,17,6,14,9,18,11,14,8,10,11,12,19,16,15,7,3,11,19,9]
Output:
25
Expected:
28

Is your code right?or the test case is wrong?

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