This post is completed by 1 user

  • 0
Add to List
Hard

244. Dynamic programming - Remove Boxes Problem | leetcode

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 the 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 the 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 the rest of the string using recursion.
  3. Leave the option chosen in 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 results from steps 2 and step 3.

See the diagram below for more understanding.

Time Complexity: 2n.




public class Main { public static 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) { long startTime = System.currentTimeMillis(); String input = "123321"; System.out.println("Max Profit: " + removeBox(input)); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end-startTime)/1000 + " seconds"); } }



def remove_box(input_str): profit = 0 if input_str is None or len(input_str) == 0: return 0 if len(input_str) == 1: return 1 start_index = 0 end_index = 0 while start_index < len(input_str): c = input_str[start_index] count = 0 while end_index < len(input_str) and c == input_str[end_index]: end_index += 1 count += 1 # Now we have a choice to select that chunk or not if end_index >= len(input_str): profit = max(profit, count * count) else: profit = max(profit, remove_box(input_str[:start_index] + input_str[end_index:]) + count * count) start_index = end_index return profit if __name__ == "__main__": input_str = "123321" print("Max Profit:", remove_box(input_str))



package main import ( "fmt" ) func removeBox(input string) int { profit := 0 if input == "" { return 0 } if len(input) == 1 { return 1 } startIndex := 0 endIndex := 0 for startIndex < len(input) { c := input[startIndex] count := 0 for endIndex < len(input) && c == input[endIndex] { endIndex++ count++ } // Now we have a choice to select that chunk or not if endIndex >= len(input) { profit = max(profit, count*count) } else { profit = max(profit, removeBox(input[:startIndex]+input[endIndex:])+count*count) } startIndex = endIndex } return profit } func max(a, b int) int { if a > b { return a } return b } func main() { input := "123321" fmt.Println("Max Profit:", removeBox(input)) }

If we look closely at 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 results of the subproblems and whenever we make a recursive call, first check if the subproblem is already solved, if yes then use it.




import java.util.HashMap; public class Main { 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) { Main r = new Main(); 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"); } }



class Main: def __init__(self): self.map = {} def remove_box(self, input_str): profit = 0 if input_str is None or len(input_str) == 0: return 0 if input_str in self.map: return self.map[input_str] if len(input_str) == 1: return 1 start_index = 0 end_index = 0 while start_index < len(input_str): c = input_str[start_index] count = 0 while end_index < len(input_str) and c == input_str[end_index]: end_index += 1 count += 1 # Now we have a choice to select that chunk or not if end_index >= len(input_str): profit = max(profit, count * count) else: profit = max(profit, self.remove_box(input_str[:start_index] + input_str[end_index:]) + count * count) start_index = end_index self.map[input_str] = profit return profit if __name__ == "__main__": r = Main() input_str = "123321" print("Max Profit:", r.remove_box(input_str))



package main import ( "fmt" ) type Main struct { Map map[string]int } func NewMain() *Main { return &Main{ Map: make(map[string]int), } } func (m *Main) RemoveBox(input string) int { profit := 0 if input == "" { return 0 } if val, ok := m.Map[input]; ok { return val } if len(input) == 1 { return 1 } startIndex := 0 endIndex := 0 for startIndex < len(input) { c := input[startIndex] count := 0 for endIndex < len(input) && c == input[endIndex] { endIndex++ count++ } if endIndex >= len(input) { profit = max(profit, count*count) } else { profit = max(profit, m.RemoveBox(input[:startIndex]+input[endIndex:])+count*count) } startIndex = endIndex } m.Map[input] = profit return profit } func max(a, b int) int { if a > b { return a } return b } func main() { r := NewMain() input := "123321" fmt.Println("Max Profit:", r.RemoveBox(input)) }

Output:

Max Profit: 12
Time taken: 0 seconds