57. Word Wrap Problem

Given n words with given lengths and a maximum line width M, arrange the words into lines (in order, without reordering or splitting a word) to minimize the total cost. Each line's cost, except the last line, is (extra spaces on that line)^2, where extra spaces = M - (sum of word lengths on that line + one space between each pair of words on that line). The last line has zero cost as long as it fits. Print the minimum total cost.

Input: The first line contains the integer n (number of words). The second line contains n space-separated integers - each word's length. The third line contains the integer M - the maximum line width. Output: Print a single integer - the minimum total cost of arranging the words into lines.

1 <= n <= 200, 1 <= word length, M <= 1000, every individual word length <= M

The squared-cost penalty specifically discourages a few lines with LOTS of extra space rather than many lines with a little extra space each (since squaring punishes large gaps disproportionately) - understanding this shapes intuition for why certain break points are chosen over others.

Arrange a sequence of words into lines of a fixed maximum width, choosing where to break lines so that the total 'wasted space' penalty is as small as possible. Brute force: Try every possible way of choosing line breaks directly (which words go on which line) - this branches combinatorially over all possible partition points, impractical for larger word counts without memoization. Optimised: Defining minCost(i) as a function of only 'which word we're starting from' captures the reusable insight that the best arrangement of the REMAINING words never depends on how earlier lines were broken - computing minCost from the end backward (or via memoized recursion) ensures each starting position's best cost is computed exactly once.

Recursively try every possible way of breaking the sequence of words into lines: at each starting word, try extending the current line by one more word for as long as it still fits within M, and for each valid line length recurse on the remaining words, adding that line's cost (extra spaces squared) to whatever the rest of the words cost. Take the minimum total cost over all these branching choices, treating the very last line as free. This explores an exponential number of ways to partition the word sequence into lines, since every prefix boundary is an independent decision point. Time: O(2^n) Space: O(n)

Notice the recursion only ever depends on the starting word index, so memoize the minimum cost of optimally wrapping words[i..n-1] in a table indexed by i. For each i, still try every possible end of the first line j (as long as it fits), but now reuse previously solved subproblems instead of recomputing them, cutting the exponential blowup down to a polynomial number of distinct states. Each state does O(n) work trying line endings, giving an overall quadratic algorithm that is dramatically faster than the brute-force recursion while still exploring the same set of choices. Time: O(n^2) Space: O(n^2)

Build the DP bottom-up from the last word to the first: dp[i] is the minimum cost of wrapping words[i..n-1], where dp[n] = 0. For each i, walk j forward from i accumulating the running line length and, the moment it would exceed M, stop; along the way compute each candidate line's cost directly (avoiding a separately precomputed n x n cost matrix) and take dp[i] = min over valid j of cost(i,j) + dp[j+1], with the very last line's cost forced to 0. This keeps the same O(n^2) worst-case work as the memoized version but needs only a single 1-D dp array instead of a full cost table, and breaks out of the inner loop as soon as a line width is exceeded, which is meaningfully leaner in both space and constant factor. Time: O(n^2) Space: O(n)

1. Define minCost(i) as the minimum total cost to arrange words starting from word i through the end. 2. For each possible 'this line ends at word j' choice (as long as the words from i to j actually fit within the width M), compute this line's cost (extra space squared, or zero if it's the last line) plus minCost(j+1) for everything after. 3. Take the best (minimum) choice of j for each i, working backward from the end of the words toward the beginning.

Time: O(n²) - for each of the n starting positions, trying every possible ending position for that line costs up to O(n), giving O(n²) total. Space: O(n), for the memoized minCost array.

A word whose length equals M (fills a line exactly, since every word length is guaranteed <= M); the last line always costing zero as long as it fits; n up to 200 words and M up to 1000, testing O(n^2) DP performance.

Be ready to explain why the LAST line's cost is defined as zero (as long as it fits) rather than squared extra-space like other lines - this asymmetry is explicitly part of the problem's own cost model and easy to overlook.