I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width). The input text is a sequence of $n$ words of lengths $l_1, l_2,...,l_n$, measured in characters, which are to be printed neatly on a number of lines that hold a maximum of $M$ characters each. No word exceeds the line length, so that $l_i\le M$ for $i=1, 2, ... ,n$. The criterion of neatness is as follows. If a given line contains words $i$ through $j$ , where $i \le j$ , and exactly one space appears between words, then the number of extra space characters at the end of the line is $M-j+i-\sum_{k=i}^j l_k$ which must be nonnegative so that the words fit on the line. The goal is to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of $n$ words neatly. Analyze the running time and space requirements of your algorithm. [1]
in order to appreciate dynamic programming (which I found can run in $O(n)$ time), I wonder what if we use a brute force search instead? So my actual question is what's the size of the search space if we're to use brute force search?
I tried this: Words must be printed in fixed order. Suppose no empty line is allowed, we know the $i+1$ th words must come right after the $i$ th word and that they may either be on the same line or on adjacent line. We want to find the total number of arrangement of the word sequence. Consider the set of all arrangements $A_i$ of a sequence of $i$ words and the binary variable $b(a,i+1)$ is $1$ only if the $i+1$ th word can be on the same line as the $i$ th word in the arrangement $a\in A_i$. Then $$ |A_n| = |A_{n-1}| + \sum_{a\in A_{n-1}} b(a,n) $$ which of course implies $|A_{n-1}| \le |A_n| \le 2|A_{n-1}| $ and since $|A_1|=1$ we have $1 \le |A_n| \le 2^{n-1}=O(2^n)$.
However I'm not sure this is correct especially I haven't well defined what "arrangement" is using $M$ and $l_1,...,l_n$ ...
[1] Introduction To Algorithms, MIT
(1) Naïve way to try all Possibilities & then check whether that arrangement is valid.
Then each new word can be put on current line or on the next line. Hence , we get $2^n$ ways to arrange the words & then we have to validate each arrangement & then print out the neatest way.
This Naive Brute force is $O(2^n)$
(2) Even with Brute force , we can be a little Non-Naïve way to try all Possibilities with a small check.
Let average word length be $W$
When we have to put a new word , we can try to put it on the Current line or on the next line.
But when we have enough words on the current line , the new word is going to over-shoot & hence we can not put it there & will have to put it on the next line.
On average , $M/W$ words fit on a line.
hence $n/(M/W)=nW/M$ times we will have 1 choice , every time else we will have 2 choices.
Hence $2^{n-nW/M}$ ways will have to be checked.
This Non-Naïve Brute force is $O(2^{n-nW/M})$
Example , average word length is $5$ , line length is $20$ , then we will get Non-Naïve Brute force is $O(2^{0.75n})$
Example , average word length is $10$ , line length is $500$ , then we will get Non-Naïve Brute force is $O(2^{0.98n})$
Nothing will beat the Dynamic Programming Case