# Dynamic programming – Remove Boxes Problem

Objec­tive:  Given a number of boxes with different colors represented by different positive numbers. You need to remove all the boxes in several rounds, each time you can choose continuous boxes with the same color (means with same numbers, composed of k boxes, k >= 1), remove them and get k*k points.
Write an algorithm to get the maximum points by removing all the boxes.

Reference: https://leetcode.com/problems/remove-boxes/description/

Example

```1233211

Remove 33 – Profit = 2*2 = 4, Remaining = 12211
Remove 22 – Profit = 4 + 2*2 = 8, Remaining = 111
Remove 11 - Profit = 3*3 + 8 = 17
```

We will try to club identical numbers so that when we will remove those together, will get the maximum profit since if we are removing x boxes then profit will be x*x.

Approach:

Recursion:

1. Will try every option and choose the best one.
2. Start from index 0, pick the maximum identical numbers possible, add the profit and solve rest of the string using recursion.
3. Leave the option chosen in the step 2 and follow the same approach taken in step 2. Solve the remaining string (which includes the option from step 2) recursively.
4. Pick the maximum among result from step 2 and step 3.

See the diagram below for more understanding. Time Complexity: 2n.

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class RemovesBoxRecursion { public int removeBox(String input) { int profit =0; //System.out.println(input); if (input == null || input.length() == 0) { return 0; } if(input.length()==1){ return 1; } int start_index = 0; int end_index = 0; while (start_index < input.length()) { char c = input.charAt(start_index); int count = 0; while (end_index=input.length()){ profit = Math.max(profit,count*count); }else{ profit = Math.max(profit, removeBox(input.substring(0, start_index) + input.substring(end_index, input.length())) + count * count); } start_index=end_index; } return profit; } public static void main(String[] args) { RemovesBoxRecursion r = new RemovesBoxRecursion(); long startTime = System.currentTimeMillis(); String input = "123321"; System.out.println("Max Profit: " + r.removeBox(input)); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end–startTime)/1000 + " seconds"); } }

Dynamic Programming-

If we look closely the diagram above we are solving many sub problems recursively. Here we will use Top-down approach of dynamic programming. We will use Hash Map to store the sub problems results and whenever we make a recursive call, first check if the sub problem is already solved, if yes then use it.

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.HashMap; public class RemoveBoxesDP { HashMap map = new HashMap(); public int removeBox(String input) { int profit =0; //System.out.println(input); if (input == null || input.length() == 0) { return 0; } if(map.containsKey(input)) return map.get(input); if(input.length()==1){ return 1; } int start_index = 0; int end_index = 0; while (start_index < input.length()) { char c = input.charAt(start_index); int count = 0; while (end_index=input.length()){ profit = Math.max(profit,count*count); }else{ profit = Math.max(profit, removeBox(input.substring(0, start_index) + input.substring(end_index, input.length())) + count * count); } start_index=end_index; } map.put(input,profit); return profit; } public static void main(String[] args) { RemoveBoxesDP r = new RemoveBoxesDP(); long startTime = System.currentTimeMillis(); String input = "123321"; System.out.println("Max Profit: " + r.removeBox(input)); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end–startTime)/1000 + " seconds"); } }

Output:

Max Profit: 12
Time taken: 0 seconds

### 1 thought on “Dynamic programming – Remove Boxes Problem”

1. In the example above
“Remove 11” should be “Remove 111”