Memoization DFS C++


  • 32
    W

    Getting memory limit errors for the last input, so sad. I read some of the top submissions and found out the reason: I was using STL vector instead of a C array....

    Thanks to one of the top submission, which used the same idea as me, I have cleaned my code.

    ======================= Explanation ===========================
    First Attempt
    The initial thought is straightforward, try every possible removal and recursively search the rest. No doubt it will be a TLE answer. Obviously there are a lot of recomputations involved here. Memoization is the key then. But how to design the memory is tricky. I tried to use a string of 0s and 1s to indicate whether the box is removed or not, but still getting TLE.

    One step further
    I think the problem of the approach above is that there are a lot of unnecessary computations (not recomputations). For example, if there is a formation of ABCDAA, we know the optimal way is B->C->D->AAA. On the other hand, if the formation is BCDAA, meaning that we couldn't find an A before D, we will simply remove AA, which will be the optimal solution for removing them. Note this is true only if AA is at the end of the array. With naive memoization approach, the program will search a lot of unnecessary paths, such as C->B->D->AA, D->B->C->AA.

    Therefore, I designed the memoization matrix to be memo[l][r][k], the largest number we can get using lth to rth (inclusive) boxes with k same colored boxes as rth box appended at the end. Example, memo[l][r][3] represents the solution for this setting: [b_l, ..., b_r, A,A,A] with b_r==A.

    The transition function is to find the maximum among all b_i==b_r for i=l,...,r-1:

    memo[l][r][k] = max(memo[l][r][k], memo[l][i][k+1] + memo[i+1][r-1][0])

    Basically, if there is one i such that b_i==b_r, we partition the array into two: [b_l, ..., b_i, b_r, A, ..., A], and [b_{i+1}, ..., b_{r-1}]. The solution for first one will be memo[l][i][k+1], and the second will be memo[i+1][r-1][0]. Otherwise, we just remove the last k+1 boxes (including b_r) and search the best solution for lth to r-1th boxes. (One optimization here: make r as left as possible, this improved the running time from 250ms to 35ms)

    The final solution is stored in memo[0][n-1][0] for sure.

    I didn't think about this question for a long time in the contest because the time is up. There will be a lot of room for time and space optimization as well. Thus, if you find any flaws or any improvements, please correct me.

    class Solution {
    public:
        int removeBoxes(vector<int>& boxes) {
            int n=boxes.size();
            int memo[100][100][100] = {0};
            return dfs(boxes,memo,0,n-1,0);
        }
        
        int dfs(vector<int>& boxes,int memo[100][100][100], int l,int r,int k){
            if (l>r) return 0;
            if (memo[l][r][k]!=0) return memo[l][r][k];
    
            while (r>l && boxes[r]==boxes[r-1]) {r--;k++;}
            memo[l][r][k] = dfs(boxes,memo,l,r-1,0) + (k+1)*(k+1);
            for (int i=l; i<r; i++){
                if (boxes[i]==boxes[r]){
                    memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i,k+1) + dfs(boxes,memo,i+1,r-1,0));
                }
            }
            return memo[l][r][k];
        }
    };
    

  • 0
    V

    Thanks, can you elaborate in the idea of how to solve? It looks like a dp problem,how did you choose the state to store and how you came up with the recursion?


  • 2
    Z

    Could you explain what your state here means? I feel like it's quite similar to LC 312 Burst Balloons, but can't figure out a good way to cache state.


  • 1

    @zzwcsong I also think this problem is very close to the balloon one.


  • 0
    K

    I guess the meaning of code like this.

    class Solution {
    private :
    	int cache[100][100][100] = { 0, };
    	int dp(vector<int>& boxes, int l, int r, int choiced)//choiced means the num of boxes user choose which is same color with boxes[l] in range [0,  l)
    	{
    		if (l > r)	return 0;
    		int& ret = cache[l][r][choiced];
    		if (ret)return ret;
    		ret = (choiced + 1) * (choiced + 1) + dp(boxes, l + 1, r, 0);// remove boxes user choose which are same color with left most box(boxes[l])
    		for (int mid = l + 1; mid <= r; mid++)
    		{
    			if (boxes[mid] != boxes[l])continue;
    			ret = max(ret, (dp(boxes, l + 1, mid - 1, 0) + dp(boxes,mid, r, choiced + 1)));
    			//dp(boxes, l + 1, mid - 1, 0) new dp in range [l+1,mid - 1]
    			//dp(boxes,mid, r, choiced + 1) inc choiced box(boxes[l]) and dp in range[mid,r]
    			//ㄴ>(boxes[l] == boxes[mid]) so, choiced is increased in range [0,mid)
    		}
    		return ret;
    	}
    public:
    	int removeBoxes(vector<int>& boxes) 
    	{
    		return dp(boxes,0, boxes.size() - 1, 0);
    	}
    };
    

  • 0
    W

    @victorj8 I have updated the answer, hope you can get my idea.


  • 0
    W

    @zzwcsong I was thinking the same but couldn't find a link between the two problems.


  • 0
    Z

    @waterbucket You could see my modified solution here : Java Preprocessing DFS + Memoization, less space needed.

    After preprocessing the boxes array

            // preprocessing
            // boxes [1,1,1,3,3,2,3,3,3,1,1] would become
            // colors : [1,3,2,3,1]
            // lens :   [3,2,1,3,2]
    

    It looks more similar to LC312 Burst Balloon, since now it only has interaction with adjacent color blocks, although we still need third dimension to keep track the current length of continuous same color blox.


  • 0
    W

    @zzwcsong Thanks for sharing this great idea. I think now we can establish the link between the two problems!


  • 0

    could you please explain more on the meaning of memo[l][r][k] and how the equation come? thank you so much!


  • 0
    W

    @victorzhang21503 I don't know which part is confusing you. memo[l][r][k] means the largest number we could get with this array: [b_l,...,b_r, A,A,...,A] where the number of A is k, and A=b_r.
    This idea comes from the thought of reducing unnecessary computations. If we have multiple As at the end, and there is no other A in front of b_r, the most we could get by removing A is (k+1)^2 (including b_r).


  • 2
    B

    I think further optimization can be done as following (C++, 13ms):

    class Solution {
    public:
    int removeBoxes(vector<int>& boxes) {
    int n = boxes.size();
    unordered_map<int, int> memo;
    return dfs(boxes, memo, n, 0, n-1, 0);
    }

    int dfs(vector<int>& boxes, unordered_map<int, int>& memo, int n, int l, int r, int k){
        if (l > r) return 0;
        int key = (l*n+r)*n+k;
        if (memo.find(key) != memo.end()) return memo[key];
    
        while (l < r && boxes[r] == boxes[r-1]) { r--; k++; }
        while (l < r && boxes[l] == boxes[r]) { l++; k++; }
        
        key = (l*n+r)*n+k;
        memo[key] = dfs(boxes, memo, n, l, r-1, 0) + (k+1)*(k+1);
        for (int i = l; i < r; i++){
            if (boxes[i] == boxes[r]) {
                while (i+1 < r && boxes[i+1] == boxes[r]) i++;
                memo[key] = max(memo[key], dfs(boxes, memo, n, l, i, k+1) + dfs(boxes, memo, n, i+1, r-1, 0));
            }
        }
        return memo[key];
    }
    

    };


  • 0

    I don't understand what does k==0 means, according to your statement:
    "memo[l][r][k], the largest number we can get using lth to rth (inclusive) boxes with k same colored boxes as rth box appended at the end", I thought k should be at least be 1, cause there must be at least 1 same colored boxes at the end.


  • 0
    W

    @pinkfloyda k here means additional box same as rth box.


  • 0
    B

    I get MLE with dp[105][105][105]. However dp[100][101][101] is okay. Sigh....


  • 0
    H

    Add a greedy rule.

        int dfs(vector<int>& boxes,int memo[100][100][100], int l,int r,int k){
            if (l>r) return 0;
            if (memo[l][r][k]!=0) return memo[l][r][k];
    
            while (r>l && boxes[r]==boxes[r-1]) {r--;k++;}
            memo[l][r][k] = dfs(boxes,memo,l,r-1,0) + (k+1)*(k+1);
            for (int i=l; i<r; i++){
                // go as right as possible
                while (boxes[i]==boxes[r]){
                    i++;
                }
                if( i > l && boxes[i-1] == boxes[r] ) {
                    memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i-1,k+1) + dfs(boxes,memo,i,r-1,0));
                }
                    
            }
            return memo[l][r][k];
        }
    

  • 0

    @zzwcsong THis one is much harder.


Log in to reply
 

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