Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic programming — Remove Boxes Problem

Objec­tive:  Given a num­ber of boxes with dif­fer­ent col­ors rep­re­sented by dif­fer­ent pos­i­tive num­bers. You need to remove all the boxes in sev­eral rounds, each time you can choose con­tin­u­ous boxes with the same color (means with same num­bers, com­posed of k boxes, k >= 1), remove them and get k*k points.
Write an algo­rithm to get the max­i­mum points by remov­ing all the boxes.

Ref­er­ence: https://leetcode.com/problems/remove-boxes/description/

Exam­ple

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 iden­ti­cal num­bers so that when we will remove those together, will get the max­i­mum profit since if we are remov­ing x boxes then profit will be x*x.

Approach:

Recur­sion:

  1. Will try every option and choose the best one.
  2. Start from index 0, pick the max­i­mum iden­ti­cal num­bers pos­si­ble, add the profit and solve rest of the string using recursion.
  3. Leave the option cho­sen in the step 2 and fol­low the same approach taken in step 2. Solve the remain­ing string (which includes the option from step 2) recursively.
  4. Pick the max­i­mum among result from step 2 and step 3.

See the dia­gram below for more understanding.

Time Com­plex­ity: 2n.

Code:

Dynamic Pro­gram­ming–

If we look closely the dia­gram above we are solv­ing many sub prob­lems recur­sively. Here we will use Top-down approach of dynamic pro­gram­ming. We will use Hash Map to store the sub prob­lems results and when­ever we make a recur­sive call, first check if the sub prob­lem is already solved, if yes then use it.

Code:

Out­put:

Max Profit: 12
Time taken: 0 seconds

You may also like...