将句子分隔成行的最低成本

/*
 * 题目思路：
 * 给定一个句子和一个最大行宽度，将句子分隔成多行，要求每行的宽度尽可能均匀，最小化宽度与平均宽度的偏差。
 * 使用Java Stream方法，首先计算每个单词在不同位置分割的最小成本。
 * 然后使用Stream方法进行处理和计算。
 */
import java.util.*;
import java.util.stream.*;

public class SentenceSplitterStream {
    public int minCostToSplit(String sentence, int maxWidth) {
        String[] words = sentence.split(" ");
        int n = words.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n] = 0;

        IntStream.range(0, n).boxed().sorted(Comparator.reverseOrder()).forEach(i -> {
            int lineLength = 0;
            for (int j = i; j < n; j++) {
                lineLength += words[j].length();
                if (j > i) lineLength++; // 加上空格
                if (lineLength > maxWidth) break;
                int cost = (maxWidth - lineLength) * (maxWidth - lineLength);
                if (j == n - 1) cost = 0;
                dp[i] = Math.min(dp[i], cost + dp[j + 1]);
            }
        });
        return dp[0];
    }

    public static void main(String[] args) {
        SentenceSplitterStream splitter = new SentenceSplitterStream();
        String sentence = "This is a sample sentence for splitting";
        int maxWidth = 10;
        System.out.println(splitter.minCostToSplit(sentence, maxWidth));
    }
}