A DP Solution & An Extra Thought of Using Dancing Links


  • 2
    X

    Suppose we have an array A : [8, 6, 2, 6, 6, 3, 2, 3, 2, 2]; (length is 10)
    Try to express the problem that
    Calculating the biggest sum of removing boxes in A starting from index i up to j(i<=j) as G(i,j)
    Then we may consider G(i,j+1) based on the solution of G(i,j).
    Let G(i,j).V be the solution of problem G(i,j)'s biggest sum, and G(i,j).L be its continuous number of the last element(e.g A[j]) when getting G(i,j).V , for example, A[0~3] = [8 6 2 6] , we can easily get the biggest sum by removing elements as the following : 8, 2, 6 6, thus G(0,3).V = 1^2 + 1^2 + 2^2 = 6, and G(0,3).L = the continuous number of A [3] 's count when removing. = 2
    Now let's consider G(i,j+1)'s solution,

    • If A[j+1]=A[j], then we can easily get that, G(i,j+1).V = G(i,j).V - G(i,j).L^2 + (G(i,j).L + 1)^2 = G(i,j).V + 2*G(i,j).L + 1, and respectively, G(i,j+1).L = G(i,j).L + 1.
      This is not very hard to prove.Say we'll calculate G(0,4), we find that A[4]=6=A[3], so just append A[4] to the last of A[3] in G(i,j)'s solution,we get G(0,4)'s solution :8,2,6 6 6.Thus G(0,4) = G(0,3).V + 2*G(0,3).L + 1 = 6 + 2*2 + 1 = 11,and G(0,4).L = G(0,3).L + 1 = 3.

    • If A[j+1]!=A[j], then there are two conditions of removing A[j+1]:

                    1.removing A[j+1] alone
                          Under this condition, A[i+1] does not have to  be removed with any other element.Simply let S as its solution,then S.V = G(i,j).V + 1, and S.L = 1.
                    2.removing A[j+1] with an element in A[i~j] so that we can get a bigger count of A[j+1] to calculate the square of the count.Let r>=0 && r<=j-i-1 and A[i+r] = A[j+1],(e.g.  r is offset from i such that  A[i+r] = A[j+1],and i+r <= j -1 , because A[j+1]!=A[j])
                          Under this condition, A[j+1] has to be removed with A[i+r],so elements in range from i+r+1 to j must be removed before A[j+1].Let F(i,j,r) be the problem that "Calculating the biggest sum of removing boxes in A starting from index i up to j(i<=j) &&  A[j]==A[i+r] && A[j] is removed together with A[i+r]"
    

    For instance, consider G(0,8).If we already have solved G(0,7), then A[8]=2 A[7]=3, A[8]!=A[7] , and A[8]=A[6]=A[2]=2. We can

    • 1 remove A[8] alone
      or
    • 2.remove A[8] together with A[6], raising new problem F(0,8,6)
    • 3.remove A[8] together with A[2], raising new problem F(0,8,2)

    So we know G(0,8).V = max { G(0,7).V + 1,F(0,8,6).V, F(0,8,2).V }
    Generally, if A[j+1]!=A[j], then G(i,j+1).V = max {G(i,j).V + 1, max{ F(i,j+1,r) where A[i+r]==A[j+1] && r>=0 && r<=j -i-1} }
    Now let's consider F(i,j,r).In this type of problem, A[i+r+1 ~ j-1] must be removed before A[i+r] and A[j] , so it is the problem of G(i+r-1,j-1),and then if we solved G(i,i+r), then by adding 1 to G(i,i+r).V we get the solution of removing A[j] together with A[i+r],
    So
    F(i,j,r).V = G(i+r+1,j-1).V + G(i,i+r).V + 2*G(i,i+r).L + 1, and
    F(i,j,r).L = G(i,i+r).L + 1

    To conclude,we get formula:
    G(i,j+1).V = max {G(i,j).V + 1, max{ F(i,j+1,r) where A[i+r]==A[j+1] && r>=0 && r<=j -i-1} }
    G(i,j+1).L = 1 if G(i,j+1).V = G(i,j).V + 1 else G(i,j+1).L=F(i,j+1,r).L where G(i,j+1),V=F(i,j,r).V
    F(i,j,r).V = G(i+r+1,j-1).V + G(i,i+r).V + 2*G(i,i+r).L + 1,
    F(i,j,r).L = G(i,i+r).L + 1

    <DP solution ended>

    An Extra Thought
    I've solved the sudoku problem by using Knuth's Dancing Links Algorithm, it is a very smart data structure used in backtracing problem. So what if I express array A as a Double-Linked List like
    8 --> 6 --> 2 --> 6 --> 6 --> 3 --> 2 --> 3 --> 2 --> 2
    each time I remove a range of the same number from A.for example , I remove 6 6,then A becomes
    8 --> 6 --> 2 --> 3 --> 2 --> 3 --> 2 --> 2,
    Why I selected 6 6 instead of 2 6?Because there is a truth that builds up what I thought, each time we can only remove a single number or numbers with the same value in a continuous range.
    Now A is reduced and can be recovered using Knuth's Dancing Links later.
    By continuously removing and recovering A,we can finally traverse all possible removing orders and get the maximum result.

    Here is my accepted code, nearly 25ms time cost.

    struct Node{
    	Node *next,*previous;
    	int val;
    	int num;
    	Node(Node* next=NULL,Node* previous=NULL):next(next),previous(previous){}
    	Node(int val,int num,Node* next=NULL,Node* previous=NULL):next(next),previous(previous),val(val),num(num){}
    
    	void insertNext(int val,int num)
    	{
    		Node *newnode=new Node(val,num,this->next,this);
    		if(newnode->next)
    			newnode->next->previous = newnode;
    		this->next = newnode;
    	}
    	//remove all node after thisnode such that the count of number can not exceed biggestnum
    	static void eliminate(Node *thisnode,int biggestnum)
    	{
    		Node *p=thisnode->next;
    		while(p && biggestnum >= p->num) p = p->next;
    		/**
    		 * We should free those nodes here,but I did not.
    		 * make a note to mark this problem
    		 */
    		thisnode->next = p;
    		if(p)p->previous = thisnode;
    	}
    
    	static void update(Node* thisnode,int newval,int newnum)
    	{
    		while(true)
    		{
    			if(newval > thisnode->val)
    			{
    				if(newnum >= thisnode->num)
    				{
    					thisnode->val = newval;
    					thisnode->num = newnum;
    					eliminate(thisnode,newnum);
    				}else{//insert this to next
    					Node *newnode = new Node(newval,newnum,thisnode,thisnode->previous);
    					thisnode->previous = newnode;
    					if(newnode->previous)
    						newnode->previous->next = newnode;
    				}
    				return;//ended
    			}else if(newval == thisnode->val)
    			{
    				if(newnum > thisnode->num) {thisnode->num = newnum;eliminate(thisnode,newnum);}
    				return;
    			}else{
    				if(newnum <= thisnode->num)return;
    				else if(thisnode->next == NULL)
    				{
    					Node *newnode = new Node(newval,newnum,NULL,thisnode);
    					thisnode->next = newnode;
    					return;
    				}else{
    					thisnode = thisnode->next;//continue to next
    				}
    			}
    		}
    	}
    };
    
    class Solution
    {
    public:
    	int removeBoxes(vector<int>& boxes)
    	{
    		row = (int) boxes.size();
    		col = row;
    		C = new std::map<int,Node>[row * col]; //C[i][j][k]
    		for(int i=0;i<row;i++)
    		{
    			for(int j=0;j<col;j++)
    			{
    				int base = i*col + j;
    				if(i > j)continue;
    				else if( i == j)
    				{
    					C[base].insert({0,Node()});
    					C[base][0].insertNext(1, 1);
    				}else{
    					C[base].insert({j-i,Node()});
    					C[base][j-i].insertNext(-1, -1);
    				}
    			}
    		}
    		this->boxes = &boxes;
    		solveRangeg(0,row-1);
    		int val = C[row-1][row - 1].next->val;
    		return val;//C[0][row-1][row-1][VAL]
    	}
    	/**
             * formula for F(i,j,k)
    	 * i<j &&  0<=k<=j-i-2  && A[i+k]==A[j], A[j]!=A[j-1]
    	 */
    	void solveRangef(int i,int j,int k)
    	{
    		int base=i*col + j;
    		if(C[base].find(k)!=C[base].end())return; //already has i,j,k solved
    		if(i<0 || i>=row || j<0 || j>=col || i>=j)return;
    
    		C[base].insert({k,Node()});
    		C[base][k].insertNext(-1, -1);
    
    		solveRangeg(i,i+k);
    		solveRangeg(i+k+1,j-1);
    
    		int diff = j -i -k-2;
    		int base2=(i+k+1)*col + (j-1);
    		int isolateVal=diff>=0?C[base2][diff].next->val:0;
    
    		int base1=i*col + (i+k);
    		Node *n=C[base1][k].next;
    		Node *basenode=C[base][k].next;
    		while(n)
    		{
    			Node::update(basenode,n->val + 2*n->num + 1 + isolateVal,n->num + 1);
    			n=n->next;
    		}
    	}
    	/**
             * formula for G(i,j)
    	 */
    	void solveRangeg(int i,int j)
    	{
    		int base=i*col+j;
      		if(i<0 || i>=row || j<0 || j>=col || i>=j || C[base][j-i].next->val!=-1)return;
    
    
    		solveRangeg(i,j-1);
    
    		std::vector<int> &A = *boxes;
    		Node *basenode=C[base][j-i].next;
    		int base1 = i*col + (j-1);
    		Node *base1node=C[base1][j-i-1].next;
    		if(A[j]==A[j-1])
    		{
    			Node *n=base1node;
    			while(n)
    			{
    				Node::update(basenode, n->val + 2*n->num + 1, n->num + 1);
    				n=n->next;
    			}
    
    			return;
    		}
    
    		Node::update(basenode,base1node->val + 1,1);
    		for(int r=j-i-2;r>=0;r--)
    		{
    			if(A[r+i]!=A[j])continue;
    			solveRangef(i,j,r);
    			Node *n=C[base][r].next;
    			while(n)
    			{
    				Node::update(basenode,n->val,n->num);
    				n = n->next;
    			}
    		}
    	}
    
    
    	std::map<int,Node> *C;
    	std::vector<int> *boxes;
    	int row;
    	int col;
    };
    

Log in to reply
 

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