Remove Boxes Problem


Description

LeetCode Problem 546.

You are given several boxes with different colors represented by different positive numbers.

You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= 1), remove them and get k * k points.

Return the maximum points you can get.

Example 1:

1
2
3
4
5
6
7
8
Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

Example 2:

1
2
Input: boxes = [1,1,1]
Output: 9

Example 3:

1
2
Input: boxes = [1]
Output: 1

Constraints:

  • 1 <= boxes.length <= 100
  • 1 <= boxes[i]<= 100


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
	// initialized to 0, mem[left][right][k] means value from boxes[left]~boxes[right] followed by 
    // k same color boxes. Follow does not mean strictly consecutive boxes, 
    // for example, [1, 3, 2, 3, 4], 3 can be 
    // followed by the other 3 because we can remove 2 first
    int mem[100][100][100]; 
    
    int removeBoxes(vector<int>& boxes) {
        return DFS(boxes,0,boxes.size()-1,0);
    }
    
    int DFS(vector<int>& boxes, int l,int r,int k){
        if (l>r) return 0; 
        if (mem[l][r][k]) 
        	// if we have calculated this DFS result, return it
        	return mem[l][r][k]; 
        
        // box[l][r] result is box[l][r-1]+(k+1)^2
        mem[l][r][k] = DFS(boxes,l,r-1,0) + (k+1)*(k+1); 

        for (int i=l; i<r; i++) 
        	// go through each box from left
        	// check for same color box as boxes[r]
            if (boxes[i]==boxes[r]) 
            	// if we found same color box,
                // then we have a chance to get a higher value by group 
                // boxes[l]~boxes[i] and boxes[r] together, plus the 
                // value from boxes[i+1]~boxes[r-1]
                mem[l][r][k] = max(mem[l][r][k], DFS(boxes,l,i,k+1) + DFS(boxes,i+1,r-1,0)); 
        return mem[l][r][k];
    }
};




Related Posts

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...