CODEWITHSUNDEEP
javaalgorithmdynamic-programming
daydreamer
daydreamer

Reputation: 91999

Dynamic Programming Breaking a String

The goal is to calculate the cost of breaking the string at the break points given by the user. So lets assume the following: The length of String = 10 so lengthArray = [1,2,3,4,5,6,7,8,9,10] and BreakPointArray = [5, 3, 2, 6, 1]. Now we do not have to change the order of the breaks given by the user.

I am able to figure out the tree structure for this problem

enter image description here

So the total cost of breaking the String at the breakPoints given = 10+5+5+3+2 = 25 However I am not able to come up with the implementation part. Below is my approach :

I start from BreakPoint = 5 and divide the lengthArray into

leftLength = [1,2,3,4,5]

and

rightLength = [6,7,8,9,10]

at BreakPoint = 3 , I check that it should come under leftLength Array so again I divide leftLength into 2 parts

leftLength1 = [1, 2,3]

and

rightLength1 = [4,5]

at BreakPoint = 2, come under leftLength1 so again divide into 2 parts

leftLength2 = [1,2] and

rightLength2 = [3]

Now I get stuck when BreakPoint = 6, since it comes under rightLength above. Can someone please help how can i keep track of all the partitions I have done . How can i go back to first rightLength array to compute cost for breakPoint 6. I am trying to implement this Java.

Upvotes: 1

Views: 1680

Answers (1)

Egor Skriptunoff
Egor Skriptunoff

Reputation: 89

Sorry, this is Lua, but DP algorithm is clear enough

-- input constants
local L = 0
local R = 10
local BreakPoints = {5, 3, 2, 6, 1}

-- fill the arrays
local NearestRight = {}
local NearestLeft = {}
for k = L, R do
   NearestRight[k] = R
   NearestLeft[k] = L
end

-- calculating cost
local cost = 0
for _, BreakPoint in ipairs(BreakPoints) do
   local left = NearestLeft[BreakPoint]
   local right = NearestRight[BreakPoint]
   cost = cost + (right - left)
   for k = left + 1, BreakPoint - 1 do
      NearestRight[k] = BreakPoint
   end
   for k = BreakPoint + 1, right - 1 do
      NearestLeft[k] = BreakPoint
   end
end
print(cost)   -- outputs 25

Time complexity is O(cost)

Upvotes: 2

Related Questions