# 2052. Minimum Cost to Separate Sentence Into Rows
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-cost-to-separate-sentence-into-rows/description/
## 思路
基本型II dp里面的分组题
要注意的地方在于最后一行 不管结尾有多少空格 都可以忽略不计 所以要分开讨论
## Code

class Solution:
    def minimumCost(self, sentence: str, k: int) -> int:
        strs = sentence.split()
        dp = [0]*(len(strs)+1)
        for i in range(len(strs)):
            # when strs[i] it occupies a whole line
            if i==len(strs)-1: dp[i+1] = dp[i]
            else: dp[i+1] = (k-len(strs[i]))**2 + dp[i]
            currLen = len(strs[i])
            for j in range(i-1, -1, -1):
                # add strs[j] to the current line
                currLen += len(strs[j])+1
                if currLen>k: break
                else:
                    if i==len(strs)-1: dp[i+1] = min(dp[i+1], dp[j])
                    else: dp[i+1] = min(dp[i+1], dp[j]+(k-currLen)**2)
        return dp[-1]