2. [10 marks] Suppose you are developing the prototype of a web browser. At some stage, you need to design a way of breaking an English paragraph into lines to display it in the browser; naturally you would like to make the lines look good. Suppose that each line always displays a set of words, that is, we do not hyphenate words for line breaks. To define this problem, we are given a list of n words, W = {w1, w2, . . . , wn}, representing a paragraph, where wi is the i-th word in the paragraph. For each word wi , we are given its length li . We also know the maximum number, m, of characters that can be displayed in each line of the browser. We know in advanced that wi m for each i. Our goal is to break W into lines in a way that minimizes a total cost penalizing the wasted space. The cost of breaking a single line to display the words wi , wi+1, . . . , wj has cost:

if this cost if nonnegative (to understand this function, think of (j i) as the number of space characters needed to separate these words; then c(i, j) can be viewed as the cube of the wasted space of this line). If this cost is negative, then we set c(i, j) = + instead, to show that the words {wi , wi+1, . . . , wj} do not fit in a single line. Furthermore, if this cost is positive and j = n, that is, this positive cost is for the last line used to display this paragraph, then we set c(i, j) = 0. That is, we do not penalize the wasted space in the last line. To calculate the total cost penalizing the wasted space, you simply sum up the above cost of each line used to display the paragraph. Now, use dynamic programming to design an efficient algorithm to solve this problem optimally. In this question, you are only required to report the value of the minimum total cost.

k=i k=i