给定一个由空格分隔的单词组成的字符串 sentence 和一个整数 k。你的任务是将 sentence 分成多行，每行中的字符数最多为 k。你可以假设 sentence 不以空格开头或结尾，并且 sentence 中的单词由单个空格分隔。
你可以通过在 sentence 中的单词间插入换行来分隔 sentence 。一个单词不能被分成两行。每个单词只能使用一次，并且单词顺序不能重排。同一行中的相邻单词应该由单个空格分隔，并且每行都不应该以空格开头或结尾。
一行长度为 n 的字符串的分隔成本是 (k - n)2 ，总成本就是除开最后一行以外的其它所有行的分隔成本之和。
- 以
sentence = "i love leetcode"和k = 12为例：<ul> <li>将<code>sentence</code> 分成 <code>"i"</code>, <code>"love"</code>, 和<code>"leetcode"</code> 的成本为 <code>(12 - 1)<sup>2</sup> + (12 - 4)<sup>2</sup> = 185</code>。</li> <li>将<code>sentence</code> 分成 <code>"i love"</code>, 和<code>"leetcode"</code> 的成本为 <code>(12 - 6)<sup>2</sup> = 36</code>。</li> <li>将<code>sentence</code> 分成 <code>"i"</code>, 和<code>"love leetcode"</code> 是不可能的，因为 <code>"love leetcode"</code> 的长度大于 <code>k</code>。</li> </ul> </li>
返回将sentence分隔成行的最低的可能总成本。
示例 1:
输入: sentence = "i love leetcode", k = 12 输出: 36 解释: 将 sentence 分成"i", "love", 和"leetcode" 的成本为 (12 - 1)2 + (12 - 4)2 = 185. 将 sentence 分成"i love", 和"leetcode" 的成本为 (12 - 6)2 = 36. 将 sentence 分成"i", "love leetcode" 是不可能的，因为 "love leetcode" 的长度为 13. 36是最低的可能总成本，因此返回它
示例 2:
输入: sentence = "apples and bananas taste great", k = 7 输出: 21 解释: 将 sentence 分成"apples", "and", "bananas", "taste", 和"great" 的成本为 (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 = 21. 21是最低的可能总成本，因此返回它
示例 3:
输入: sentence = "a", k = 5 输出: 0 解释: 最后一行的成本不包括在总成本中，而sentence只有一行，所以返回0
提示:
1 <= sentence.length <= 50001 <= k <= 5000sentence中每个单词长度最大为k.sentence只包含小写字母和空格.sentence不会以空格开头或结尾.sentence中的单词以单个空格分隔.
class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
@cache
def dfs(i):
if s[-1] - s[i] + n - i - 1 <= k:
return 0
ans, j = inf, i + 1
while j < n and (t := s[j] - s[i] + j - i - 1) <= k:
ans = min(ans, (k - t) ** 2 + dfs(j))
j += 1
return ans
t = [len(w) for w in sentence.split()]
n = len(t)
s = list(accumulate(t, initial=0))
return dfs(0)class Solution {
private static final int INF = Integer.MAX_VALUE;
private int[] memo;
private int[] s;
private int n;
public int minimumCost(String sentence, int k) {
String[] words = sentence.split(" ");
n = words.length;
s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + words[i].length();
}
memo = new int[n];
Arrays.fill(memo, INF);
return dfs(0, k);
}
private int dfs(int i, int k) {
if (memo[i] != INF) {
return memo[i];
}
if (s[n] - s[i] + n - i - 1 <= k) {
memo[i] = 0;
return 0;
}
int ans = INF;
for (int j = i + 1; j < n; ++j) {
int t = s[j] - s[i] + j - i - 1;
if (t <= k) {
ans = Math.min(ans, (k - t) * (k - t) + dfs(j, k));
}
}
memo[i] = ans;
return ans;
}
}class Solution {
public:
const int inf = INT_MAX;
int n;
int minimumCost(string sentence, int k) {
istringstream is(sentence);
vector<string> words;
string word;
while (is >> word) words.push_back(word);
n = words.size();
vector<int> s(n + 1);
for (int i = 0; i < n; ++i) s[i + 1] = s[i] + words[i].size();
vector<int> memo(n, inf);
return dfs(0, k, s, memo);
}
int dfs(int i, int k, vector<int>& s, vector<int>& memo) {
if (memo[i] != inf) return memo[i];
if (s[n] - s[i] + n - i - 1 <= k) {
memo[i] = 0;
return 0;
}
int ans = inf;
for (int j = i + 1; j < n; ++j) {
int t = s[j] - s[i] + j - i - 1;
if (t <= k) ans = min(ans, (k - t) * (k - t) + dfs(j, k, s, memo));
}
memo[i] = ans;
return ans;
}
};func minimumCost(sentence string, k int) int {
words := strings.Split(sentence, " ")
n := len(words)
inf := math.MaxInt32
s := make([]int, n+1)
for i, word := range words {
s[i+1] = s[i] + len(word)
}
memo := make([]int, n)
for i := range memo {
memo[i] = inf
}
var dfs func(int) int
dfs = func(i int) int {
if memo[i] != inf {
return memo[i]
}
if s[n]-s[i]+n-i-1 <= k {
memo[i] = 0
return 0
}
ans := inf
for j := i + 1; j < n; j++ {
t := s[j] - s[i] + j - i - 1
if t <= k {
ans = min(ans, (k-t)*(k-t)+dfs(j))
}
}
memo[i] = ans
return ans
}
return dfs(0)
}