难度: Medium
Submission
运行时间: 36 ms
内存: 16.2 MB
class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
words = sentence.split(' ')
endings = [-1]*(len(words)+1)
for i, w in enumerate(words):
endings[i+1] = endings[i] + 1 + len(w)
N = len(words)
dp = [inf]*N
for i in range(N-1, -1, -1):
if endings[-1] - endings[i] - 1 <= k:
dp[i] = 0
else:
dp[i] = min((k-endings[j+1]+endings[i]+1)**2 + dp[j+1]
for j in takewhile(lambda j: endings[j+1] - endings[i] - 1 <= k, range(i,N))
)
return dp[0]
# m-i-1 +
# S[i] = min(S[m] + (k-L[i..m])
# L[i,j] = N[j] - N[i-1] - 1
Explain
该题解采用动态规划方法来解决问题。首先，通过`endings`数组计算每个词到句首的累积长度，包括空格。`dp[i]`表示从单词i开始到句子末尾的最小成本。从句子的末尾开始计算dp值，逐步向前推进。如果从当前单词i到句尾的所有单词长度和小于等于k，则dp[i]为0（因为所有单词都可以放在一行）。否则，需要计算将单词分成多行时的最小成本，即考虑每一个可能的断点j，计算从i到j的单词放在一行时的剩余空间的平方（作为成本），加上从j+1开始的最小成本。最终，dp[0]将给出整个句子的最低分隔成本。
时间复杂度: O(N^2)
空间复杂度: O(N)
class Solution:
def minimumCost(self, sentence: str, k: int) -> int:
words = sentence.split(' ') # 分割句子为单词列表
endings = [-1]*(len(words)+1) # 初始化endings数组
for i, w in enumerate(words): # 计算每个位置的累积长度
endings[i+1] = endings[i] + 1 + len(w)
N = len(words)
dp = [float('inf')]*N # 初始化dp数组，用无穷大表示尚未计算的状态
for i in range(N-1, -1, -1): # 从后向前计算dp值
if endings[-1] - endings[i] - 1 <= k: # 如果当前位置到句尾的所有单词长度和小于等于k
dp[i] = 0 # dp[i]设为0
else: # 计算分割成本
dp[i] = min((k-endings[j+1]+endings[i]+1)**2 + dp[j+1]
for j in takewhile(lambda j: endings[j+1] - endings[i] - 1 <= k, range(i,N)))
return dp[0] # 返回从第一个单词开始的最小成本
Explore
在动态规划中，`dp[i]`数组用于存储从第i个单词开始到句子末尾的最小成本。初始化为无穷大是因为在计算之前，我们不知道具体的成本值，而无穷大可以保证在后续的最小值比较过程中，任何实际计算出的成本都会被选为更小值。这是一种常见的动态规划初始化方法，用以确保正确地更新成本值。
`endings`数组通过累加每个单词的长度及其之前的空格来构建。初始化`endings[0]`为-1，因为第一个单词前没有空格。对于每个单词，`endings[i+1]`等于`endings[i]`加上当前单词的长度加1（代表单词前的空格）。这样，`endings`数组能够准确反映从句首到当前单词的累积长度，包括单词间的空格。
`takewhile`函数从一个迭代器中取元素直到指定的条件不再满足。在这个算法中，它用来迭代所有可能的断点j，条件是单词i到单词j的长度总和（包括空格）不超过k。这样，使用`takewhile`可以有效地限制循环范围，避免不必要的计算，提高效率。
当单个单词长度超过k时，由于在计算dp时检查了从i到N的长度是否小于等于k，若没有满足这一条件的j存在，dp[i]将保持为初始的无穷大，表示无法在不超过k的限制下将这些单词放在一行内。当所有单词的长度和刚好等于k时，从dp的计算逻辑中可以看出，由于整体长度等于k，dp[i]会被设置为0，表示无额外成本，所有单词恰好放在一行。