Below you will see recursive solutions to problems 15-4 and 15-9. Your problem is to complete the process of converting these recursive solutions into dynamic programming solutions. Also, engineer your solutions so that they produce the optimal values and the set of choices needed to produce those optimal values. For problem 15-4 you should be able to generate the actual list of line breaks that produce the lowest penalty. For problem 15-9 you should be able to generate the actual sequence of cuts that give the lowest total cost.
Problem 15-4
The recursive solution shown below makes use of the extra-space function, which computes the number of extra spaces we would have at the end of a given line if that line held words i through j, inclusive.
Using this function we can easily write the following recursive function that tries to compute the lowest penalty possible for laying out words i through j in a paragraph.
lowest-penalty(i,j)
// First, check for a base case: all the words fit
// on the same line. You can tell this is happening
// because the extra-space at the end of the line will
// be non-negative.
if extra-space(i,j) >= 0
if j == n // Lines that end with the last word
return 0 // are another special case.
else
return (extra-space(i,j))^3
// If we are not in the base case, we have to try breaking
// the words into two sub-paragraphs. Try all possible ways
// to break the span into two sub-paragraphs.
min = infinity
for k = i+1 to j-1
penalty = lowest-penalty(i,k) + lowest-penalty(k+1,j)
if penalty < min
min = penalty
return min
Our first attempt at a recursive solution is to write a function optimal-break that recursively tries breaking the portion of the string from begin to end (inclusive) at a set of breaks specified in an array named cuts.
optimal-break(begin,end,cuts)
if cuts is empty
return 0
total-cost = end - begin + 1
cost = infinity
for each cut in cuts
try = optimal-break(begin,cut,before-cut(cut,cuts)) +
optimal-break(cut+1,end,after-cut(cut,cuts))
if try < cost
cost = try
return cost + total-cost
The problem with this solution is that it does not have the correct parameter structure. Since one of its parameters is a list and not an integer, we can not readily convert this solution to dynamic programming.
The solution is to start by doing something that also isn't correct. We will absorb the information about where the substring starts and ends into the list of cuts itself. For example, if we are told to break a string with characters 1 through 16 at cut points {7, 10, 12}, we will create a new cuts array that looks like {0, 7, 10, 12, 16}. Using 0 instead of 1 to specify the beginning of the range works better and makes it easier to set up the recursion.
optimal-break(cuts)
// Base case: if the length of the cuts array is 2
// we don't actually have any cuts to make.
if cuts.length == 2
return 0
// Now comes the recursion.
total-cost = cuts[cuts.length] - cuts[1]
cost = infinity
for k = 2 to cuts.length - 1
try = optimal-break(cuts[1..k]) +
optimal-break(cuts[k,cuts.length])
if try < cost
cost = try
return cost + total-cost
This leads to a much cleaner recursive solution, but is still not right. The problem still is that the single parameter to the recursive optimal-breaks function is a list and not an integer.
The way out of this problem is to use a standard trick. Instead of passing around arrays as parameters, we create one global cut list and just pass around indices to that list.
optimal-break(i,j)
if j == i+1
return 0
total-cost = cuts[j] - cuts[i]
cost = infinity
for k = i+1 to j-1
try = optimal-break(i,k) + optimal-break(k,j)
if try < cost
cost = try
return cost + total-cost