Question

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

English Version

题目描述

给定一个由空格分隔的单词组成的字符串 sentence 和一个整数 k。你的任务是将 sentence 分成多行，每行中的字符数最多为 k。你可以假设 sentence 不以空格开头或结尾，并且 sentence 中的单词由单个空格分隔。

你可以通过在 sentence 中的单词间插入换行来分隔 sentence 。一个单词不能被分成两行。每个单词只能使用一次，并且单词顺序不能重排。同一行中的相邻单词应该由单个空格分隔，并且每行都不应该以空格开头或结尾。

一行长度为 n 的字符串的分隔成本是 (k - n)2 ，总成本就是除开最后一行以外的其它所有行的分隔成本之和。

• 以 sentence = "i love leetcode" 和k = 12为例：
  • 将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" 的长度大于 k。

返回_将_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 <= 5000
• 1 <= k <= 5000
• sentence 中每个单词长度最大为 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)
}