c++ DFS Solution with Explanation.


  • 2
    S

    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.


  • 0
    Z

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


  • 0
    X

    @supersj said in c++ DFS Solution with Explanation.:

    #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?


Log in to reply
 

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