We are given an array of $N$ words $W[1\dots N],$ and a length array $L[1\dots N]$, where each $L[i]$ denotes the length (number of characters) of $W[i]$. We are also given a line width $M$, which is assumed to be greater than every $L[i]$. We would like to print all these words, in the same order, without breaking any word across multiple lines.
To illustrate, suppose $M=15, N=7,$ and the words and lengths are as given below:
$\begin{array}{|c|l|c|l|} \hline \textbf{Word} & can & you & solve&this&using&dynamic&programming? \\\hline\textbf{Length}&3&3&5&4&5&7&12 \\\hline \end{array}$
Here are four example ways of laying out this text. Note that there should be a space between adjacent words on the same line.
$\begin{array}{|c|l|c|l|} \hline \textbf{Layout 1} & \textbf{Layout 2} &\textbf{Layout 3}&\textbf{layout 4} \\\hline \text{can} & \text{can you} &\text{Can you solve}&\text{Can you solve}\\ \text{you}&\text{solve this}&\text{this using}&\text{this using dynamic}\\ \text{solve}&\text{using dynamic}&\text{dynamic}&\text{programming?}\\ \text{this}&\text{programming?}&\text{programming?}&\text{}\\ \text{using}&\text{}&\text{}&\text{}\\ \text{dynamic}&\text{}&\text{}&\text{}\\ \text{programming?}&\text{}&\text{}&\text{} \\\hline \end{array}$
Of the four layouts above, Layouts $1, 2,$ and $3$ are valid since each line has at most $15$ characters, while Layout $4$ is invalid since line $2$ requires $18$ characters, which will spill over beyond the line width of $15$.
Each valid layout has a cost, computed as follows. Let the text be spread out over $K$ lines. For each line $i$, let $s_i$ be the number of spaces that are appended at the end of the line to make the line exactly $M$ characters long. The cost of the layout is $\sum^K_{i=1} s^3_i.$
For Example, Layout $1$ has cost
$(15-3)^3+(15-3)^3+(15-5)^3+(15-4)^3+(15-5)^3+(15-7)^3+(15-12)^3=7326$
Layout $2$ has cost
$(15-7)^3+(15-10)^3+(15-13)^3+(15-12)^3=672$
Layout $3$ has cost
$(15-13)^3+(15-10)^3+(15-7)^3+(15-12)^3=672$
We can use dynamic programming to compute the smallest cost of any layout for $N$ words $W[1\dots N]$ with lengths given by $L[1\dots N]$, and line width $M$. For $1\underline< i \underline<N$, let $C[i]$ denote the minimum cost of any layout for words $W[i\dots N]$.
- Write a recurrence relation for $C[i]$ in terms of $C[i+1],C[i+2],\dots,C[N]$.
- Implement your recurrence as a dynamic programming algorithm.
- How much time and space does your algorithm need, in terms of $N$?
