這是一個家庭作業問題，但我完全失去了。我有一個不可能的時間來弄清楚這個子問題是什麼：我嘗試過一種貪婪的方法，我試圖在一行上建立一些單詞等等，而我無法想出任何東西。任何人都可以提供任何見解嗎？動態規劃：最小化空白
問題：考慮到單詞列表轉換爲文本typset程序。該程序將這些字打印到長度爲W的行上，使得該行末尾的額外空格的數量使得包含單詞i至j的行包含W-j + i-SUM（單詞i至j中的字符）。編寫一個動態編程算法，使每行上額外空間的平方和最小。
我相信你應該有辦法如下：
- >找到一個線長1的最佳解決方案和節約價值（這應該是微不足道的）。
- >找到一個線長2這樣的最佳解決方案：
的每一個字看看它們是否適合。如果他們確實計算剩餘空間並使用該空間的最佳解決方案（將剩餘1或0個空間）。
...（這一路做W）
- >找到一個線路長度W的這樣的最佳解決方案爲：每字看看它們是否適合
。如果他們這樣做，計算出剩餘空間，並使用該剩餘空間的最佳解決方案（因爲它是小於W使您已經計算出它。）
動態規劃是解決了在簡單的方法等問題的一個很好的選擇開發商。
，我們可以用它來解決這個問題的動態規劃方法如下。首先，如果所有單詞都符合一行，那麼我們就完成了。 如果沒有，那麼我們將嘗試那些可能適合在這一行的所有可能的組合，那麼我們解決包括爲每個可能的組合 其餘單詞的子問題，我們可以通過最小化第一的成本找到最好的佈局並添加剩餘子問題的最小成本。
讓MAX（I）是其中
，這意味着詞Ĵ可能適合在開頭的行字我最大學家 我們可以填補成本c，其中C [i]爲I至N，如下的打印字的最低成本的n個元素的數組： 如果MAX（I）= n，則C [1] = 0否則：
充填陣列從上到下從n至1，將O（（M/2）n）的時間，因爲至多M/2個字可以容納在單個行上。所需的空間是O（n）。