A certain string processing language allows the programmer to break a string int

Question

A certain string processing language allows the programmer to break a string into two pieces. It costs n units of time to break a string of n dharacters into two pieces, since this involves copying the old string. A programmer wants to breaka string into many pieces, and the order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20-character string after characters 3,8, and 10. If the breaks are made in left-right order, then the first brenk costs 20 units of time, the second break costs 17 units of time, and the third break costs 12 units of time, for a total of 49 steps. If the breaks are made in right-left order, the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, for a total of only 38 steps. Give a dynamic programming algorithm that takes a list of character positions afer which to break and determines the cheapest break cost in O(n2) time. In your solution to this problem, it is suggested that you let S ss. , be the original string of length n, and let 0

Explanation / Answer

Hi,
Given the cost of breaking a string of length of n character is n, hence Ci,j will be i for ith element, therfore in the start we initialize it to i,
for i=1 to p do
   Ci,j = i
for k=1 to p-1 do
  for i=1 to p-k do
   Ci,j+k= bi+k+1 - b + min(Ci+1,j+k,CI,J+K+1)
   if k>1
then for j=i+1 to i+k-1 do
   Ci,j+k=min( Ci,i+k,Ci+1,j+k)
SO, the logic here is to first find divide the problem into overlapping sub problems, that is in this, if we know the min cost of the i-1th iteration, we can find the cost ffor ith iteration by Ci-1,j-1 + min cut now
that is what the first loop does by picking the min of the smaller sub problems.

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.