CareerCup

say we have all the optimal printing between the words in the range [i, i + k], i = 1, ... n - k
to find the optimal printing between the words in the range [i, i + k + 1], i = 1, ..., n - k - 1
for each [i, i + k + 1], consider the optimal printing of word[i] + optimal printing [i + 1, i + k + 1], and the optimal printing of optimal printing [i, i + k] + word[i + k + 1], and the better one is the optimal printing of word[i, i + k + 1].
time is n^2
space is n

I see the problem a little bit different. Giving words[N] and a function S(i,j) to be an extra space characters of printing words[i] to words[j] in a line of size M (the formula is given in the problem statement). Imagine an NxN table each of which cell(i,j) filled with S(i,j). We can see that the bottom half are N/A as i !< j, cell[i,i] is an extra space from printing only word[i] in a line. The top right are likely be a negative values since there are too many words than the line of size M. For a large paragraph of word[N] we can imagine a diagonal strip lining from top left to bottom right to be a valid S(i,j).

Now, let draw a vertical line OPT(j) to represent the optimal printing giving the first j words. OPT(1) will be a base case of printing the word[0] in a line. For other j, OPT(j) = Min S(i,j) + OPT(i-1) for i=0 to j and S(i,j) is valid. S(i,j) represent the last j-i words in the paragraph and OPT(i-1) be the optimal printing words[0] to words[i-1].

We can have DP compute from OPT[1] to OPT[N] with O(N^2) in both time and space complexity as you need S(i,j) to be pre executed.

Let the substring be l_0, l_1, ..., l_{N-1}. We have:
===
Subproblems: Let T[k, x] be the minimum cube-sum that can be attained in a paragraph containing the sequence l_x, l_{x+1}, ..., l_N using k lines.

===
Recursion:

T[k, x]:

if (k >= 2): min( T[k-1, x+1] + (M - l_x - l_{x+1})^3, T[k-1, x+2] + (M - l_x - l_{x+1} - l_{x+2})^3, ...); the ...s go until the value being cubed is < 0.

if (k = 1): min( (M - l_x)^3, (M - l_x - l_{x+1})^3, (M - l_x - l_{x+1} - l_{x+2})^3, ...); the ...s go until the value being cubed is < 0.

if (k = 0): (M - l_x - l_{x+1} - ...)^3

We should return: max(T[0, N-1}, T[0, N-2], ...).

===
Motivation: if we're given l_x l_x+1 l_x+2 ... l_n, we want to see where to place the next carriage return after l_x. So, we minimize over all possibilities and recurse. We need to keep the value of k, since the last line doesn't contribute toward the overall cubed sum.

===
Space complexity: O(n^2)
Time complexity: it takes O(n) time to compute each entry in the 2d array (assuming that computing cubed roots is O(1) ), so we have O(n^3) here. We maximize over O(n^2) entries in the end, so the total complexity is O(n^3 + n^2) => O(n^3).

I did not understand the problem.
The words have to be printed in order. Then why don't we fit as many words as possible on each line. Why would we decide not to include a word in current line and include it in next line.