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:

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() && c == input.charAt(end_index)) {
end_index++;
count++;
}
//now we have choice to select that chunk or not
if(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: " + (endstartTime)/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:

import java.util.HashMap;
public class RemoveBoxesDP {
HashMap<String,Integer> map = new HashMap<String, Integer>();
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() && c == input.charAt(end_index)) {
end_index++;
count++;
}
//now we have choice to select that chunk or not
if(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: " + (endstartTime)/1000 + " seconds");
}
}

view raw
RemoveBoxesDP.java
hosted with ❤ by GitHub


Output:

Max Profit: 12
Time taken: 0 seconds